library(dplyr)
library(data.table)
library(cowplot)
library(ggraph)
library(igraph)
source("utils.R")
knitr::opts_chunk$set(
  fig.path = "decomposition_figs/",
  fig.keep = "high",
  dev = c("pdf", "png")
)
data.dir <- "../../data/"
source("load_data.R")
'measure.vars' [Abundance_e9312, Abundance_eMED4, Abundance_NATL, Abundancee_SS120, Abundancee_9313] are not all of the same type. By order of hierarchy, the molten data value column will be of type 'character'. All measure variables not of type 'character' will be coerced to. Check DETAILS in ?melt.data.table for more on coercion.NAs introduced by coercion

Prochloroccocus

BATS

Raw relative abundance time series of ecotypes at depths:

bats[, rel.abund := abundance / sum(abundance), by = depth]
bats[, log.rel.abund := log10(rel.abund)]
ggplot(bats, aes(x = month, y = log.rel.abund)) +
  geom_path(aes(group = ecotype)) +
  facet_grid(depth ~ ecotype) +
  theme(axis.text.x = element_text(angle = 90, vjust = 0.5, hjust = 1))

Power spectrum of ecotypes at depths:

# spectral analysis per ecotype per depth
# mean per month if more than one sample
bats.depthlra <- bats[, .(mn = mean(log.rel.abund)), 
                      by = .(month, depth, ecotype)]
bats.spec <- bats.depthlra[, {
  s <- stats::spectrum(mn, plot = FALSE)
  data.table(freq = s$freq, spec = s$spec)
  }, by = .(ecotype, depth)]
# normalize so peak is 1
bats.spec[, spec := spec / max(spec), by = .(depth, ecotype)]
bats.spec[, timescale.months := 1 / freq]
ggplot(bats.spec, aes(x = timescale.months, y = spec)) +
  geom_point(size = 0.5) +
  geom_path(aes(group = ecotype)) +
  facet_grid(depth ~ ecotype) +
  geom_vline(aes(linetype = "12"), xintercept = 12, color = "blue") +
  theme(axis.text.x = element_text(angle = 90, vjust = 0.5, hjust = 1))

Blue line indicates periodicity of 1 year. Relative height of peaks gives relative magnitude of periodic fluctuations at that time scale. This shows that not all ecotypes at all depths are most strongly driven by annual cycling. E.g. e9312 apparently experiences strong annual cycling at all depths except 100. NATL experiences annual cycling at all depths but it is relatively weaker at depths 160-200.

State clustering with JSD

setkey(bats, month)
# all pairs
bats[, id := paste(month, depth, sep = "_")]
bats.ids <- unique(bats$id)
bats.div <- MakeNonRedundantPairs(bats.ids, prefix = "id")
bats.div[, c("month.i", "depth.i") := tstrsplit(id.i, "_")]
bats.div[, c("month.j", "depth.j") := tstrsplit(id.j, "_")]
# it would be nice to get distances between depths but we'll do same depth rn
# down by order of magnitude
bats.div <- bats.div[depth.i == depth.j & month.j >= month.i]
bats.div[, depth.j := NULL]
setnames(bats.div, "depth.i", "depth")
setkey(bats, id)
bats.div[, jsd := {
  if (id.i == id.j) {
    0
  } else {
    # browser()
    sd <- bats[c(id.i, id.j)]
    sd <- dcast(sd, ecotype ~ id, value.var = "rel.abund", 
                fun.aggregate = mean)
    sd <- as.matrix(sd[, -1])
    genJSD(sd)
  }
  }, by = .(id.i, id.j)]
rec <- bats.div[id.i != id.j]
setnames(rec, names(rec), sapply(names(rec), function(str) {
  if (grepl("\\.i", str)) sub("\\.i", "\\.j", str)
  else if (grepl("\\.j", str)) sub("\\.j", "\\.i", str)
  else str
}))
bats.div <- rbind(bats.div, rec)
bats.div[, distance := sqrt(jsd)]
bats.div[, ":=" (month.i = as.numeric(month.i), 
                 month.j = as.numeric(month.j))]
bats.div[, delta := month.j - month.i]
vertices <- unique(bats[, .(id, month, cal.month, depth)])
edges <- bats.div[delta == 1, .(id.i, id.j, depth = as.numeric(depth))]
graph <- graph_from_data_frame(edges, directed = FALSE, vertices)
bats.depths <- unique(bats$depth)
bats.depths <- bats.depths[order(as.numeric(bats.depths))]
names(bats.depths) <- bats.depths
bats.dms <- lapply(bats.depths, function(de) {
  d <- bats.div[depth == de]
  MakeDistMatrix(d, "id.i", "id.j")
})
fits <- lapply(bats.dms, function(dm) {
  CoordCMDS(dm)
})
xforms <- lapply(fits, function(x) {
  x$points
}) %>% rbindlist(use.names = TRUE, idcol = "depth")
eigranks <- lapply(fits, function(x) {
  x$eigrank
}) %>% rbindlist(use.names = TRUE, idcol = "depth")
eigranks[, depth := factor(depth, levels = bats.depths)]
setkey(xforms, sample)
lo <- create_layout(graph, "manual", node.positions = xforms[V(graph)$name])
mbreaks <- c(1, 3, 6, 9, 12) # Jan, plus months of solstices + equinoxes
ggraph(lo) +
  geom_edge_link(arrow = arrow(type = "closed", length = unit(3, "points")),
                 end_cap = square(length = 3, unit = "points"),
                 edge_width = 0.2) +
  geom_node_point(aes(color = cal.month), size = 0.5) +
  scale_color_gradientn(values = scales::rescale(mbreaks),
                        colors = c("blue", "green4", "yellow", "orange",
                                   "blue")
                        ) +
  facet_wrap(~ depth, ncol = 3) +
  theme_graph(base_family = "Helvetica") +
  theme(aspect.ratio = 1)

This also shows that seasonal cycling is more reproducible at some depths. For depths shallower than 100, there seems to be a reproducible path, and the composition seems to change more gradually, as can be seen in the close spacing of most consecutive timepoints. For depths 120-160, there are also reproducible paths, however, there are 3 clusters of time points (seemingly representing spring, summer/early fall, and late fall/winter) with large gaps between them, and the long leaps between clusters suggests the seasonal compositional transitions are more drastic. Finally, depths 180-200 appear more random.

Eigenvalues of MDS show that this transformation captures most of the information:

ggplot(eigranks, aes(x = rank, y = value ^2)) +
  geom_point() +
  scale_x_log10() +
  facet_wrap(~ depth, scales = "free_y")

Heatmapping the JSDs shows occupancy of stable states as dark squares of high temporal similarity along the diagonal. Recurrence of stable states show as dark off-diagonal rectangles. It is clear the time scales of stability (sizes of on-diagonal dark squares) are different for depths 1-40 and 100-160. 60-80 seem to be a hybrid of the two regimes, and 180-200 seem to go toward randomness.

bats.div[, depth := as.numeric(depth)]
ggplot(bats.div, aes(x = month.i, y = month.j)) +
  geom_tile(aes(fill = jsd)) + 
  facet_wrap(~ depth, ncol = 3) + 
  theme(aspect.ratio = 1)

David-style, JSD-based ‘autocorrelation.’ The periodicity of many of the autocorrelation functions shows strong periodic dynamics at a single time scale.

ggplot(bats.div[delta > 0], aes(x = delta, y = jsd)) +
  geom_point(size = 0.2) +
  geom_smooth() +
  facet_wrap(~ depth, ncol = 3) 

HOT

hot[, rel.abund := abundance / sum(abundance), by = depth]
hot[, log.rel.abund := log10(rel.abund)]
ggplot(hot, aes(x = month, y = log.rel.abund)) +
  geom_path(aes(group = ecotype)) +
  facet_grid(depth ~ ecotype) +
  theme(axis.text.x = element_text(angle = 90, vjust = 0.5, hjust = 1))

ggplot(eigranks, aes(x = rank, y = value ^2)) +
  geom_point() +
  scale_x_log10() +
  facet_wrap(~ depth, scales = "free_y")

Shallower depths are more stable in composition:

setkey(hot, month)
# all pairs
hot[, id := paste(month, depth, sep = "_")]
hot.ids <- unique(hot$id)
hot.div <- MakeNonRedundantPairs(hot.ids, prefix = "id")
hot.div[, c("month.i", "depth.i") := tstrsplit(id.i, "_")]
hot.div[, c("month.j", "depth.j") := tstrsplit(id.j, "_")]
# it would be nice to get distances between depths but we'll do same depth rn
# down by order of magnitude
hot.div <- hot.div[depth.i == depth.j & month.j >= month.i]
hot.div[, depth.j := NULL]
setnames(hot.div, "depth.i", "depth")
setkey(hot, id)
hot.div[, jsd := {
  if (id.i == id.j) {
    0
  } else {
    sd <- hot[c(id.i, id.j)]
    sd <- dcast(sd, ecotype ~ id, value.var = "rel.abund", 
                fun.aggregate = mean)
    sd <- as.matrix(sd[, -1])
    genJSD(sd)
  }
  }, by = .(id.i, id.j)]
rec <- hot.div[id.i != id.j]
setnames(rec, names(rec), sapply(names(rec), function(str) {
  if (grepl("\\.i", str)) sub("\\.i", "\\.j", str)
  else if (grepl("\\.j", str)) sub("\\.j", "\\.i", str)
  else str
}))
hot.div <- rbind(hot.div, rec)
hot.div[, distance := sqrt(jsd)]
hot.div[, ":=" (month.i = as.numeric(month.i), 
                 month.j = as.numeric(month.j))]
hot.div[, delta := month.j - month.i]
ggplot(hot.div, aes(x = distance)) +
  stat_ecdf(aes(color = factor(depth,
                               levels = as.character(
                                 sort(
                                   unique(
                                     as.numeric(depth)
                                     )
                                   )
                                 )
                               )
  )) +
  labs(color = "depth")

setkey(xforms, sample)
lo <- create_layout(graph, "manual", node.positions = xforms[V(graph)$name])
mbreaks <- c(1, 3, 6, 9, 12) # Jan, plus months of solstices + equinoxes
ggraph(lo) +
  geom_edge_link(arrow = arrow(type = "closed", length = unit(3, "points")),
                 end_cap = square(length = 3, unit = "points"),
                 edge_width = 0.2) +
  geom_node_point(aes(color = cal.month), size = 0.5) +
  scale_color_gradientn(values = scales::rescale(mbreaks),
                        colors = c("blue", "green4", "yellow", "orange",
                                   "blue")
                        ) +
  facet_wrap(~ depth, ncol = 3) +
  theme_graph(base_family = "Helvetica") +
  theme(aspect.ratio = 1)

Nahant

There are too many OTUs. They should probably be aggregated somehow. Here we aggregate all reads that map to the same phylum, which results in a manageable number of variables. But one could just as well aggregate at any other taxonomic level or not at all.

hot.div[, depth := as.numeric(as.character(depth))]
ggplot(hot.div, aes(x = month.i, y = month.j)) +
  geom_tile(aes(fill = jsd)) + 
  facet_wrap(~ depth, ncol = 3) + 
  theme(aspect.ratio = 1)

phyla %>% 
  group_by(phylum) %>% 
  mutate(freq = scales::rescale(freq)) %>% 
  ggplot(aes(x = as.numeric(day), y = freq)) +
  theme(strip.text = element_text(size = 10),
        axis.text.x = element_text(angle = 90, vjust = 0.5, hjust = 1)
        ) +
  scale_y_continuous(breaks = c(0, 0.5, 1)) +
  geom_line(aes(group = phylum)) +
  facet_wrap(~ phylum, ncol = 4) +
  labs(y = "frequency (normalized)")

We can look at the spectral density of the phyla time series. Phyla with peaks in the low frequencies exhibit slow fluctuations. It seems there really are slow and broad-spectrum taxa at this level.

phyla.spec <- phyla %>%
  dcast(day ~ phylum, value.var = "freq") %>% 
  select(-day) %>% 
  stats::spectrum(plot = FALSE)
phyla.spec <- data.table(cbind(phyla.spec$freq, phyla.spec$spec)) %>% 
  setnames(c("freq", phyla.spec$snames)) %>% 
  melt(id.vars = "freq", variable.name = "phylum")
phyla.spec %>% 
  group_by(phylum) %>% 
  mutate(value = value / sum(value)) %>% 
  ggplot(aes(x = freq, y = phylum)) +
  labs(x = "frequency (1/day)") +
  geom_tile(aes(fill = value)) 

R there statez?

Are there qualitative coarse-grainable compositional states in the Nahant data?

phyla[, day := as.character(day)]
days <- unique(phyla[, day])
day.div <- data.table(expand.grid(day.i = days, day.j = days))
day.div[, ":=" (day.i = as.character(day.i), 
                           day.j = as.character(day.j))]
setkey(phyla, day)
day.div[, jsd := {
  if (day.i == day.j) {
    0
  } else {
    sd <- phyla[c(day.i, day.j)]
    sd <- dcast(sd, phylum ~ day, value.var = "freq")
    m <- as.matrix(sd[, 2:3])
    d <- genJSD(m)
    d
  }
}, by = .(day.i, day.j)]
day.div[, distance := sqrt(jsd)]

Layout the samples by Jensen-Shannon distance using mds algorithm. Color by day so as to see temporal progression. Hierarchically cluster by JS distance.

edges <- cbind(days[-length(days)], days[-1])
graph <- graph_from_data_frame(edges, directed = FALSE,
                               vertices = data.table(id = days,
                                                     day = as.numeric(days)))
dm <- MakeDistMatrix(day.div, "day.i", "day.j")
fit <- CoordCMDS(dm)
xform <- fit$points
# order
setkey(xform, sample)
xform <- xform[V(graph)$name]
layout <- create_layout(graph, "manual", node.positions = xform)
p1 <- ggraph(layout) +
  geom_edge_link(arrow = arrow(type = "closed", 
                               length = unit(5, "points")),
                 edge_width = 0.2,
                 end_cap = square(length = 5, unit = "points")
                 ) +
  geom_node_point(aes(color = day)) +
  theme_graph(base_family = "Helvetica") +
  scale_color_distiller(palette = "Spectral") 
# clustering
hc <- hclust(dist(dm))
dendro <- as.dendrogram(hc)
dendro <- dendrapply(dendro, function(d) {
  if (is.leaf(d)) {
    attr(d, "nodePar") <- list(day = as.numeric(attr(d, "label")))
  }
  d
})
p2 <- ggraph(dendro, "dendrogram") +
  geom_edge_elbow() +
  # geom_node_text(aes(filter = leaf, color = day, label = day), angle = 90, size = 2) +
  geom_node_point(aes(filter = leaf, color = day)) +
  scale_color_distiller(palette = "Spectral") +
  theme_graph(base_family = "Helvetica") #+
  # theme(aspect.ratio = 1)
plot_grid(p1, p2, nrow = 2, align = "hv", labels = c("A", "B"))

These data show a clear transition between stable states around day 240. These two states form the two major branches at the lowest level of the hierarchical clustering.

The eigenvalues of the MDS transform show that information is well preserved:

ggplot(fit$eigrank, aes(x = rank, y = value ^ 2)) +
  geom_point()

Statistics of dynamics

Distribution of daily compositional step sizes. The Maxwell-Boltzmann/lognormal shape to the density at \(\Delta(t) = 1\) suggests that under this time resolution the change in composition behaves like some kind of random walk, with a characteristic step size and rare changes of larger magnitude.

day.div <- day.div[, day.delta := as.numeric(day.j) - as.numeric(day.i)]
p1 <- ggplot(day.div[day.delta == 1,], aes(x = distance)) +
  stat_bin(bins = 30) 
p2 <- ggplot(day.div[day.delta == 1], aes(x = as.numeric(day.i), y = distance)) +
  geom_point() + 
  # stat_smooth() + 
  labs(x = "day i")
plot_grid(p1, p2, nrow = 2, labels = "AUTO", align = "hv")

day.div[day.delta > 0] %>% 
  mutate(group = as.factor(floor(day.delta / 10) * 10),
         ddelta = as.factor(day.delta %% 10)) %>% 
  ggplot(aes(x = distance)) +
  stat_bin(bins = 30, position = "identity") +
  scale_color_brewer(palette = "Spectral") +
  theme(axis.text.x = element_text(angle = 90, vjust = 0.5, hjust = 1, 
                                   size = 7
                                   ),
        axis.text.y = element_text(size = 6)
        ) +
  facet_grid(group ~ ddelta, scales = "free_y")

Compositional distance as function of interval. This is sort of an autocorrelation spectrum. There are no peaks in this ‘spectrum’ suggesting there are no characteristic time scales of periodic behavior. Since there is only one major state transition in these data, it could also be interpreted as the period of state transitions being longer than the observation time, when interpreted as periodic.

br <- days[seq(1, length(days), by = 5)]
ggplot(day.div, aes(x = day.i, y = day.j)) +
  geom_tile(aes(fill = distance)) +
  scale_x_discrete(breaks = br) +
  scale_y_discrete(breaks = br) +
  theme(aspect.ratio = 1,
        axis.text.x = element_text(angle = 90, vjust = 0.5, hjust = 1))

tl <- day.div[day.delta > 0, .(mn.dist = mean(distance)), by = day.delta]
p0 <- ggplot(day.div[day.delta > 0], aes(x = day.delta, y = distance)) 
p1 <- p0 + geom_point(size = 1) + 
  # stat_smooth(aes(linetype = "mean"))  +
  geom_line(aes(y = mn.dist, linetype = "mean"), tl, color = "blue", size = 2) +
  labs(linetype = "", x = "interval (days)")
p2 <- p0 + stat_bin_2d(binwidth = c(1, 0.01)) + labs(x = "interval (days)")
plot_grid(p1, p2, nrow = 2, align = "hv", labels = "AUTO")

Human

David et al

david <- fread(paste0(data.dir, "david/david.otus"), 
               col.names = c("sample", "otu", "count")
               )
# parse subject and timepoints
david.samples <- unique(david[, .(sample)])
david.samples[, c("subject", "day") := tstrsplit(sample, "_")]
# log transform otu counts
david[, log.count := log(count + 1)]
# split by subject
david.subjects <- unique(david.samples$subject)
names(david.subjects) <- david.subjects
# create tables of day-day divergences
david.div <- data.table(expand.grid(sample.i = david.samples$sample,
                                    sample.j = david.samples$sample)
                        )
david.samples[, idx := 1:.N]
david.samples[, subj.idx := frank(as.numeric(day)), by = subject]
david.div <- merge(david.div, david.samples, by.x = "sample.i", 
                   by.y = "sample")
david.div <- merge(david.div, david.samples, by.x = "sample.j", 
                   by.y = "sample", suffixes = c(".i", ".j"))
david.div <- david.div[idx.j >= idx.i]
setkey(david, sample)
david.div[, jsd := {
  if (sample.i == sample.j) {
    0
  } else {
    sd <- david[c(sample.i, sample.j)]
    m <- dcast(sd, otu ~ sample, value.var = "count")
    m <- as.matrix(m[, 2:3])
    m[is.na(m)] <- 0
    genJSD(m)
  }
}, by = .(sample.i, sample.j)]
# reciprocal distances
david.div <- david.div[sample.i != sample.j] %>% 
  setnames(names(david.div), sapply(names(david.div), function(x) {
    if (grepl("idx\\.i", x)) {
      gsub("idx\\.i", "idx\\.j", x)
    } else if (grepl("idx\\.j", x)) {
      gsub("idx\\.j", "idx\\.i", x)
    } else if (grepl("\\.i", x)) {
      gsub("\\.i", "\\.j", x)
    } else if (grepl("\\.j", x)) {
      gsub("\\.j", "\\.i", x)
    } else x
  })
  ) %>%  
  rbind(david.div)
david.div[, distance := sqrt(jsd)]
david.div[, day.delta := as.numeric(day.j) - as.numeric(day.i)]
david.div[subject.i == subject.j, increment := subj.idx.j - subj.idx.i]

Merge event metadata:

david <- fread(paste0(data.dir, "david/david.otus"), 
               col.names = c("sample", "otu", "count")
               )
# parse subject and timepoints
david.samples <- unique(david[, .(sample)])
david.samples[, c("subject", "day") := tstrsplit(sample, "_")]
# log transform otu counts
david[, log.count := log(count + 1)]
# split by subject
david.subjects <- unique(david.samples$subject)
names(david.subjects) <- david.subjects
# create tables of day-day divergences
david.div <- data.table(expand.grid(sample.i = david.samples$sample,
                                    sample.j = david.samples$sample)
                        )
david.samples[, idx := 1:.N]
david.samples[, subj.idx := frank(as.numeric(day)), by = subject]
david.div <- merge(david.div, david.samples, by.x = "sample.i", 
                   by.y = "sample")
david.div <- merge(david.div, david.samples, by.x = "sample.j", 
                   by.y = "sample", suffixes = c(".i", ".j"))
david.div <- david.div[idx.j >= idx.i]
setkey(david, sample)
david.div[, jsd := {
  if (sample.i == sample.j) {
    0
  } else {
    sd <- david[c(sample.i, sample.j)]
    m <- dcast(sd, otu ~ sample, value.var = "count")
    m <- as.matrix(m[, 2:3])
    m[is.na(m)] <- 0
    genJSD(m)
  }
}, by = .(sample.i, sample.j)]
# reciprocal distances
david.div <- david.div[sample.i != sample.j] %>% 
  setnames(names(david.div), sapply(names(david.div), function(x) {
    if (grepl("idx\\.i", x)) {
      gsub("idx\\.i", "idx\\.j", x)
    } else if (grepl("idx\\.j", x)) {
      gsub("idx\\.j", "idx\\.i", x)
    } else if (grepl("\\.i", x)) {
      gsub("\\.i", "\\.j", x)
    } else if (grepl("\\.j", x)) {
      gsub("\\.j", "\\.i", x)
    } else x
  })
  ) %>%  
  rbind(david.div)
david.div[, distance := sqrt(jsd)]
david.div[, day.delta := as.numeric(day.j) - as.numeric(day.i)]
david.div[subject.i == subject.j, increment := subj.idx.j - subj.idx.i]

The magnitudes of day-to-day changes in composition don’t reflect significant events.

setkey(david.div, subject.i, subject.j)
event.lims <- events[, .(start = min(day), end = max(day)), 
                     by = .(event, subject)]
event.lims <- event.lims[!grepl("pre", event) & !grepl("post", event)]
event.lims[, event := factor(levels = c("travel", "diarrhea 1", "diarrhea 2",
                                        "Salmonella"), event)]
david.div[subject.i == subject.j & day.delta == 1] %>% 
  mutate(day.i = as.numeric(day.i)) %>% 
  setnames("subject.i", "subject") %>% 
  ggplot(aes(x = day.i, y = distance)) +
  geom_rect(data = event.lims, 
    mapping = aes(fill = event, xmin = start, xmax = end, 
                  ymin = 0.1, ymax = 1.05
                  ), inherit.aes = FALSE, alpha = 0.5) +
  geom_point() +
  facet_wrap(~ subject, nrow = 2)

Distributions of all distances for all time scales. We see that both length distributions are multimodal, indicating at least 2 compositional “length scales.” We also see that the vast majority of A distances belong to the lowest mode, while the second lowest mode of B is as high as the lowest, indicating that subject B spends a significant amount of time (relative to the length of the entire measurement).

p0 <- ggplot(david.div[subject.i == subject.j], aes(x = distance)) 
ar <- 3 / 5
cdf <- p0 + stat_ecdf(aes(color = subject.i)) + labs(y = "ECDF") +
  theme(aspect.ratio = ar)
dens <- p0 + stat_density(aes(fill = subject.i), alpha = 0.5, 
                          position = "identity") +
  theme(aspect.ratio = ar)
plot_grid(cdf, dens, nrow = 2, align = "v")

Paths

david.subjects <- c("A", "B")
names(david.subjects) <- david.subjects
setkey(david.div, subject.i, subject.j)
dm <- MakeDistMatrix(david.div, "sample.i", "sample.j")
fit <- CoordCMDS(dm)
xform <- fit$points
setcolorder(xform, c("sample", "x", "y"))
setkey(xform, sample)
# put sample labels at first 2 columns
setcolorder(david.div, c("sample.i", "sample.j",
                         names(david.div)[!(names(david.div) %in%
                                              c("sample.i", "sample.j"))])
            )
david.samples[, day := as.numeric(day)]
setcolorder(david.samples, c("sample", "subject", "day", "event", "idx", 
                             "subj.idx"))
graf <- graph_from_data_frame(
  david.div[subject.i == subject.j & increment == 1],
  directed = TRUE,
  vertices = david.samples
  )
setkey(xform, sample)
xform <- xform[V(graf)$name]
lo <- create_layout(graf, "manual", node.positions = xform)
nsize <- 1
p1 <- ggraph(lo) +
  geom_edge_link(arrow = arrow(length = unit(3, "points"), type = "closed"),
                 end_cap = square(length = 3, unit = "points"),
                 edge_width = 0.2) +
  geom_node_point(aes(color = day), size = nsize) +
  scale_color_distiller(palette = "Blues") +
  facet_nodes(~ subject) +
  theme_graph(base_family = "Helvetica") +
  theme(aspect.ratio = 1)
p2 <- ggraph(lo) +
  geom_edge_link(arrow = arrow(length = unit(3, "points"), type = "closed"),
                 end_cap = square(length = 3, unit = "points"),
                 edge_width = 0.2) +
  geom_node_point(aes(color = event), size = nsize) +
  facet_nodes(~ subject) +
  theme_graph(base_family = "Helvetica") +
  theme(aspect.ratio = 1)
plot_grid(p1, p2, nrow = 2, align = "v")

Laying both subjects along the same axes we see each subject is more similar to themselves than they are to the other subject, for the most part. The upper right represents states in which the two subjects resembled each other. Interestingly not all these points seem to be close in time. Subject B makes a brief excursion to a Subject A-like state post Salmonella.

Eigenvalues by rank:

ggplot(fit$eigrank, aes(x = rank, y = value ^ 2)) +
  geom_point()

Trees

Together

Hierarchical clustering reveals 3 major branches: characteristic of Subject A, characteristic of Subject B, and Shared Outlier State.

dm <- dcast(david.div, sample.i ~ sample.j, value.var = "distance")
rn <- dm$sample.i
dm <- dm[, -1]
dm <- as.matrix(dm)
rownames(dm) <- rn
dendro <- as.dendrogram(hclust(dist(dm)))
unique.day.events[, day := as.character(day)]
setkey(unique.day.events, subject, day)
david.samples[, day := as.character(day)]
david.samples[, state := {
  subj <- subject
  dd <- day
  unique.day.events[.(subj, dd), event]
}, by = .(subject, day)]
setkey(david.samples, sample)
dendro <- dendrapply(dendro, function(d) {
  if (is.leaf(d)) {
    samp <- attr(d, "label")
    subj <- david.samples[samp, subject]
    state <- david.samples[samp, state]
    attr(d, "nodePar") <- append(attr(d, "nodePar"), list(subject = subj, 
                                                          state = state))
  }
  d
})
ggraph(dendro, "dendrogram") +
  geom_edge_elbow() +
  geom_node_point(aes(filter = leaf, shape = subject, color = state), size = 1) +
  theme_graph(base_family = "Helvetica") +
  # theme(aspect.ratio = 1) + 
  coord_flip()

Separate

Clustering separately shows that Subject B has distinct pre- and post-Salmonella states, but the various events in Subject A’s life didn’t create alternate stable states that were significantly different.

setkey(david.div, subject.i, subject.j)
dendros <- lapply(david.subjects, function(subj) {
  sd <- david.div[.(subj, subj)]
  dm <- dcast(sd, sample.i ~ sample.j, value.var = "distance")
  rn <- dm$sample.i
  dm <- dm[, -1]
  dm <- as.matrix(dm)
  rownames(dm) <- rn
  hc <- hclust(dist(dm))
  dendro <- as.dendrogram(hc)
  return(dendro)
}
)
unique.day.events[, day := as.character(day)]
# setkey(events, subject)
setkey(unique.day.events, subject, day)
setkey(david.samples, sample)
dendros <- lapply(david.subjects, function(subj) {
  dendro <- dendros[[subj]]
  dendro <- dendrapply(dendro, function(d) {
    if (is.leaf(d)) {
      dday <- david.samples[attr(d, "label"), as.character(day)]
      ev <- unique.day.events[.(subj, dday), event]
      attr(d, "nodePar") <- append(attr(d, "nodePar"), list(
        day = as.numeric(dday),
        event = ev))
    }
    d
  })
  # propagate metadata back up the tree
  dendro <- tree_apply(dendro, function(node, children, depth, tree) {
  if (!is.leaf(node)) {
    events <- sapply(children, function(c) {
      attr(c, "nodePar")$event
    })
    events <- unique(events)
    if (length(events) == 1 & !anyNA(events)) {
      attr(node, "nodePar") <- append(attr(node, "nodePar"), list(event = events))
    } else {
      attr(node, "nodePar") <- append(attr(node, "nodePar"), list(event = NA))
    }
  }
  node
  }, direction = "up")
  dendro
})
dendro.plots <- lapply(dendros, function(dend) {
  ggraph(dend, "dendrogram", circular = TRUE) +
    geom_edge_elbow(aes(color = node2.event)) +
    geom_node_point(aes(filter = leaf, color = day), size = 0.6) +
    scale_color_distiller(palette = "Spectral") +
    theme_graph(base_family = "Helvetica") +
    theme(aspect.ratio = 1)
})
plot_grid(plotlist = dendro.plots, nrow = 2, labels = "AUTO")

Subject A doesn’t seem to have a distinct “traveling” composition. Indeed it seems the distance between traveling and US compositions doesn’t seem noticeably larger than the distance between US compositions. Meaning traveling did not destabilize the microbiome any more than baseline fluctuations while living in the US. Perhaps this is due to many OTUs remaining stable through the duration of travel.

Subject B shows clear pre- and post-Salmonella states, as reported in the original manuscript. Perhaps the post-Salmonella state is separate because of the extinction of cluster 4 (see original paper) during infection, rendering return to the pre-Salmonella state impossible?

Gordon et al (cholera)

# metadata
setkey(david.samples, subject)
events <- mapply(function(start, end, subject, event) {
  x <- data.table(day = seq(start, end, by = 1), subject = subject, 
                  event = event)
  x
}, start = c(0, 71, 80, 104, 123, 
             0, 151, 160 ),
end =   c(70, 122, 85, 113, david.samples["A", max(as.numeric(day))], 
          150, 159, david.samples["B", max(as.numeric(day))]),
subject = c("A", "A", "A", "A", "A", 
            "B", "B", "B"),
event = c("US (pre)", "travel", "diarrhea 1", "diarrhea 2", "US (post)", 
          "pre-Salmonella", "Salmonella", "post-Salmonella"),
SIMPLIFY = FALSE) %>% rbindlist(use.names = TRUE) 
# collapse event labels per day
unique.day.events <- events[, .(event = paste(event, collapse = " + ")), 
                           by = .(subject, day)]
unique.day.events[, day := as.character(day)]
david.samples <- merge(david.samples, unique.day.events, 
                       by = c("subject", "day"))
david.div <- merge(david.div, unique.day.events, by.x = c("subject.i", "day.i"),
                   by.y = c("subject", "day"))
david.div <- merge(david.div, unique.day.events, by.x = c("subject.j", "day.j"),
                   by.y = c("subject", "day"), suffixes = c(".i", ".j"))

David-style divergence matrices. Dark on-diagonal squares represent occupation of stable states. Most patients have distinct stable states.

setkey(gordon.div, subject.i, subject.j)
subjects <- sort(subjects)
names(subjects) <- subjects
gordon.div[, ":=" (hour.i = as.character(hour.i), hour.j = as.character(hour.j))]
plots <- lapply(subjects, function(subj) {
  sd <- gordon.div[.(subj, subj)]
  ts <- as.numeric(unique(sd$hour.i))
  lims <- as.character(sort(ts))
  p <- ggplot(sd, aes(x = hour.i, y = hour.j)) +
    geom_tile(aes(fill = jsd)) +
    scale_x_discrete(limits = lims) +
    scale_y_discrete(limits = lims) +
    theme(aspect.ratio = 1,
          axis.text = element_blank(),
          axis.ticks = element_blank())
})
plot_grid(plotlist = plots, ncol = 2, labels = names(plots), align = "hv")

Time-lag divergences:

gordon.div[, delta.t := as.numeric(hour.j) - as.numeric(hour.i)]
plots <- lapply(subjects, function(subj) {
  sd <- gordon.div[.(subj, subj)]
  sd <- sd[delta.t > 0]
  p <- ggplot(sd, aes(x = delta.t, y = jsd)) +
    geom_point(size = 0.1) +
    geom_smooth(color = "blue") +
    scale_x_log10() +
    labs(x = "lag (hours)")
  p
})
plot_grid(plotlist = plots, align = "hv", labels = names(plots),
          nrow = 3)
`geom_smooth()` using method = 'gam'
`geom_smooth()` using method = 'loess'
`geom_smooth()` using method = 'loess'
`geom_smooth()` using method = 'loess'
`geom_smooth()` using method = 'loess'
`geom_smooth()` using method = 'loess'
`geom_smooth()` using method = 'loess'

Distributions of divergences show that for all patients, diarrhea and recovery states are more similar to themselves than to each other (cross-state divergences are large). In most patients (except E) the recovery microbiome is actually less stable than the diarrhea microbiome: the diarrhea divergences tend to be smaller. However this could also be due to the denser temporal sampling during the diarrhea period. We should scale this by the time interval somehow, since it varies.

gordon.div[, state := {
  if (state.i == state.j) state.i
  else "cross"
}, by = .(state.i, state.j)]  
p0 <- gordon.div[(subject.i == subject.j) & (delta.t > 0)] %>% 
  ggplot(aes(x = distance))
cdf <- p0 + stat_ecdf(aes(color = state)) + facet_wrap(~ subject.i, nrow = 1) + 
  labs(y = "ECDF") +
  theme(axis.text.x = element_text(angle = 90, vjust = 0.5, hjust = 1))
dens <- p0 + stat_density(aes(fill = state), alpha = 0.3,
                          position = "identity")
dens <- dens +
  facet_wrap(~ subject.i, nrow = 1) +
  theme(axis.text.x = element_text(angle = 90, vjust = 0.5, hjust = 1))
plot_grid(cdf, dens, nrow = 2, align = "v")

Paths

MDS of all subjects simultaneously shows that diarrhea/recovery separates time points more than subject.

setkey(gordon.div, subject.i, subject.j)
setkey(gordon.samples, subject)
edges <- lapply(subjects, function(subj) {
  sd <- gordon.div[.(subj, subj)]
  ts <- as.numeric(unique(sd$hour.i))
  ts <- as.character(sort(ts))
  ej <- data.table(ti = ts[-length(ts)], tj = ts[-1])
  samps <- gordon.samples[subj, .(sample, hour)]
  samps[, hour := as.character(hour)]
  ej <- merge(ej, samps, by.x = "ti", by.y = "hour")
  ej <- merge(ej, samps, by.x = "tj", by.y = "hour", suffixes = c(".i", ".j"))
  ej[, .(sample.i, sample.j)]
}) %>% rbindlist()
graf <- graph_from_data_frame(edges,
                              directed = TRUE, vertices = gordon.samples)
dm <- MakeDistMatrix(gordon.div, "sample.i", "sample.j")
fit <- CoordCMDS(dm)
xform <- fit$points
# order
setkey(xform, sample)
xform <- xform[V(graf)$name]
lo <- create_layout(graf, "manual", node.positions = xform)
ggraph(lo) +
  geom_edge_link(arrow = arrow(type = "closed", length = unit(3, "points")),
                 edge_width = 0.2, end_cap = square(length = 3,
                                                    unit = "points")) +
  geom_node_point(aes(color = state)) +
  # scale_shape_manual(values = seq(1, length(subjects))) +
  facet_nodes(~ subject, nrow = 2) +
  theme_graph(base_family = "Helvetica") +
  theme(aspect.ratio = 1)

ggplot(fit$eigrank, aes(x = rank, y = value ^ 2)) +
  geom_point() 

All points plot show recovery and diarrhea cluster separately for all patients, with diarrhea having greater spread:

ggraph(lo) +
  geom_node_point(aes(color = state, shape = subject)) +
  scale_shape_manual(values = seq(uniqueN(gordon.samples$subject))) +
  theme_graph(base_family = "Helvetica") +
  theme(aspect.ratio = 1)

Tree

All together. Again separation is mostly diarrhea/recovery. However, some diarrhea points are closer to recovery points than they are to the majority of diarrhea points. This can also be seen in the last plot where the two ‘clouds’ enmesh.

ggraph(lo) +
  geom_node_point(aes(color = state, shape = subject)) +
  scale_shape_manual(values = seq(uniqueN(gordon.samples$subject))) +
  theme_graph(base_family = "Helvetica") +
  theme(aspect.ratio = 1)

setkey(gordon.div, subject.i, subject.j)
gordon.samples[, hour := as.character(hour)]
setkey(gordon.samples, subject, hour)
trees <- lapply(subjects, function(subj) {
  sd <- gordon.div[.(subj, subj)]
  sd <- dcast(sd, hour.i ~ hour.j, value.var = "distance")
  rn <- sd[, hour.i]
  dm <- as.matrix(sd[, -1])
  rownames(dm) <- rn
  dendro <- as.dendrogram(hclust(dist(dm)))
  # merge time data and state
  sd[, time.index := frank(as.numeric(hour.i))]
  setkey(sd, hour.i)
  dendro <- dendrapply(dendro, function(node) {
    if (is.leaf(node)) {
      labl <- attr(node, "label")
      t <- as.numeric(labl)
      time.index <- as.numeric(sd[labl, time.index])
      state <- gordon.samples[.(subj, labl), state]
      attr(node, "nodePar") <- append(attr(node, "nodePar"), 
                                      list(hour = t, time.index = time.index,
                                           state = state)
                                      )
    }
    node
  })
  # propagate state upwards through branch nodes
  dendro <- tree_apply(dendro, function(node, tree, depth, children) {
    if (!is.leaf(node)) {
      child.states <- sapply(children, function(n) {
        attr(n, "nodePar")$state
      }) %>% unique()
      if (length(child.states) == 1 & !anyNA(child.states)) {
        state <- child.states
      } else {
        state <- NA
      }
      attr(node, "nodePar") <- append(attr(node, "nodePar"),
                                      list(state = state))
    }
    node
  }, direction = "up")
  # browser()
  p <- ggraph(dendro, "dendrogram", circular = TRUE) +
    geom_edge_elbow(aes(color = node2.state)) +
    geom_node_point(aes(filter = leaf, color = time.index)) +
    scale_color_distiller(palette = "YlOrRd") +
    theme_graph(base_family = "Helvetica") +
    theme(aspect.ratio = 1, legend.key.height = unit(10, "points"))
})
plot_grid(plotlist = trees, ncol = 2, labels = names(trees))

LS0tCnRpdGxlOiAiRGVjb21wb3NpdGlvbiBvZiB0aW1lIHNjYWxlcyBpbiBtaWNyb2JpYWwgdGltZSBzZXJpZXMiCm91dHB1dDoKICBodG1sX25vdGVib29rOiBkZWZhdWx0CiAgaHRtbF9kb2N1bWVudDoKICAgIHRvYzogeWVzCiAgICB0b2NfZGVwdGg6IDIKICAgIHRvY19mbG9hdDogeWVzCiAgcGRmX2RvY3VtZW50OiBkZWZhdWx0Ci0tLQoKYGBge3Igc2V0dXAsIG1lc3NhZ2U9RkFMU0V9CmxpYnJhcnkoZHBseXIpCmxpYnJhcnkoZGF0YS50YWJsZSkKbGlicmFyeShjb3dwbG90KQpsaWJyYXJ5KGdncmFwaCkKbGlicmFyeShpZ3JhcGgpCnNvdXJjZSgidXRpbHMuUiIpCmtuaXRyOjpvcHRzX2NodW5rJHNldCgKICBmaWcucGF0aCA9ICJkZWNvbXBvc2l0aW9uX2ZpZ3MvIiwKICBmaWcua2VlcCA9ICJoaWdoIiwKICBkZXYgPSBjKCJwZGYiLCAicG5nIikKKQpkYXRhLmRpciA8LSAiLi4vLi4vZGF0YS8iCnNvdXJjZSgibG9hZF9kYXRhLlIiKQpgYGAKCiMgUHJvY2hsb3JvY2NvY3VzCgojIyBCQVRTClJhdyByZWxhdGl2ZSBhYnVuZGFuY2UgdGltZSBzZXJpZXMgb2YgZWNvdHlwZXMgYXQgZGVwdGhzOgpgYGB7ciBiYXRzLXRzLGZpZy53aWR0aD03LGZpZy5oZWlnaHQ9N30KYmF0c1ssIHJlbC5hYnVuZCA6PSBhYnVuZGFuY2UgLyBzdW0oYWJ1bmRhbmNlKSwgYnkgPSBkZXB0aF0KYmF0c1ssIGxvZy5yZWwuYWJ1bmQgOj0gbG9nMTAocmVsLmFidW5kKV0KZ2dwbG90KGJhdHMsIGFlcyh4ID0gbW9udGgsIHkgPSBsb2cucmVsLmFidW5kKSkgKwogIGdlb21fcGF0aChhZXMoZ3JvdXAgPSBlY290eXBlKSkgKwogIGZhY2V0X2dyaWQoZGVwdGggfiBlY290eXBlKSArCiAgdGhlbWUoYXhpcy50ZXh0LnggPSBlbGVtZW50X3RleHQoYW5nbGUgPSA5MCwgdmp1c3QgPSAwLjUsIGhqdXN0ID0gMSkpCmBgYAoKUG93ZXIgc3BlY3RydW0gb2YgZWNvdHlwZXMgYXQgZGVwdGhzOgpgYGB7ciBiYXRzLXNwZWMsIGZpZy5hc3A9MX0KIyBzcGVjdHJhbCBhbmFseXNpcyBwZXIgZWNvdHlwZSBwZXIgZGVwdGgKIyBtZWFuIHBlciBtb250aCBpZiBtb3JlIHRoYW4gb25lIHNhbXBsZQpiYXRzLmRlcHRobHJhIDwtIGJhdHNbLCAuKG1uID0gbWVhbihsb2cucmVsLmFidW5kKSksIAogICAgICAgICAgICAgICAgICAgICAgYnkgPSAuKG1vbnRoLCBkZXB0aCwgZWNvdHlwZSldCmJhdHMuc3BlYyA8LSBiYXRzLmRlcHRobHJhWywgewogIHMgPC0gc3RhdHM6OnNwZWN0cnVtKG1uLCBwbG90ID0gRkFMU0UpCiAgZGF0YS50YWJsZShmcmVxID0gcyRmcmVxLCBzcGVjID0gcyRzcGVjKQogIH0sIGJ5ID0gLihlY290eXBlLCBkZXB0aCldCiMgbm9ybWFsaXplIHNvIHBlYWsgaXMgMQpiYXRzLnNwZWNbLCBzcGVjIDo9IHNwZWMgLyBtYXgoc3BlYyksIGJ5ID0gLihkZXB0aCwgZWNvdHlwZSldCmJhdHMuc3BlY1ssIHRpbWVzY2FsZS5tb250aHMgOj0gMSAvIGZyZXFdCmdncGxvdChiYXRzLnNwZWMsIGFlcyh4ID0gdGltZXNjYWxlLm1vbnRocywgeSA9IHNwZWMpKSArCiAgZ2VvbV9wb2ludChzaXplID0gMC41KSArCiAgZ2VvbV9wYXRoKGFlcyhncm91cCA9IGVjb3R5cGUpKSArCiAgZmFjZXRfZ3JpZChkZXB0aCB+IGVjb3R5cGUpICsKICBnZW9tX3ZsaW5lKGFlcyhsaW5ldHlwZSA9ICIxMiIpLCB4aW50ZXJjZXB0ID0gMTIsIGNvbG9yID0gImJsdWUiKSArCiAgdGhlbWUoYXhpcy50ZXh0LnggPSBlbGVtZW50X3RleHQoYW5nbGUgPSA5MCwgdmp1c3QgPSAwLjUsIGhqdXN0ID0gMSkpCmBgYApCbHVlIGxpbmUgaW5kaWNhdGVzIHBlcmlvZGljaXR5IG9mIDEgeWVhci4KUmVsYXRpdmUgaGVpZ2h0IG9mIHBlYWtzIGdpdmVzIHJlbGF0aXZlIG1hZ25pdHVkZSBvZiBwZXJpb2RpYyBmbHVjdHVhdGlvbnMgYXQgdGhhdCB0aW1lIHNjYWxlLgpUaGlzIHNob3dzIHRoYXQgbm90IGFsbCBlY290eXBlcyBhdCBhbGwgZGVwdGhzIGFyZSBtb3N0IHN0cm9uZ2x5IGRyaXZlbiBieSBhbm51YWwgY3ljbGluZy4KRS5nLiBlOTMxMiBhcHBhcmVudGx5IGV4cGVyaWVuY2VzIHN0cm9uZyBhbm51YWwgY3ljbGluZyBhdCBhbGwgZGVwdGhzIGV4Y2VwdCAxMDAuCk5BVEwgZXhwZXJpZW5jZXMgYW5udWFsIGN5Y2xpbmcgYXQgYWxsIGRlcHRocyBidXQgaXQgaXMgcmVsYXRpdmVseSB3ZWFrZXIgYXQgZGVwdGhzIDE2MC0yMDAuCgojIyMgU3RhdGUgY2x1c3RlcmluZyB3aXRoIEpTRApgYGB7ciBiYXRzLXN0YXRlc30Kc2V0a2V5KGJhdHMsIG1vbnRoKQojIGFsbCBwYWlycwpiYXRzWywgaWQgOj0gcGFzdGUobW9udGgsIGRlcHRoLCBzZXAgPSAiXyIpXQpiYXRzLmlkcyA8LSB1bmlxdWUoYmF0cyRpZCkKYmF0cy5kaXYgPC0gTWFrZU5vblJlZHVuZGFudFBhaXJzKGJhdHMuaWRzLCBwcmVmaXggPSAiaWQiKQpiYXRzLmRpdlssIGMoIm1vbnRoLmkiLCAiZGVwdGguaSIpIDo9IHRzdHJzcGxpdChpZC5pLCAiXyIpXQpiYXRzLmRpdlssIGMoIm1vbnRoLmoiLCAiZGVwdGguaiIpIDo9IHRzdHJzcGxpdChpZC5qLCAiXyIpXQojIGl0IHdvdWxkIGJlIG5pY2UgdG8gZ2V0IGRpc3RhbmNlcyBiZXR3ZWVuIGRlcHRocyBidXQgd2UnbGwgZG8gc2FtZSBkZXB0aCBybgojIGRvd24gYnkgb3JkZXIgb2YgbWFnbml0dWRlCmJhdHMuZGl2IDwtIGJhdHMuZGl2W2RlcHRoLmkgPT0gZGVwdGguaiAmIG1vbnRoLmogPj0gbW9udGguaV0KYmF0cy5kaXZbLCBkZXB0aC5qIDo9IE5VTExdCnNldG5hbWVzKGJhdHMuZGl2LCAiZGVwdGguaSIsICJkZXB0aCIpCnNldGtleShiYXRzLCBpZCkKYmF0cy5kaXZbLCBqc2QgOj0gewogIGlmIChpZC5pID09IGlkLmopIHsKICAgIDAKICB9IGVsc2UgewogICAgIyBicm93c2VyKCkKICAgIHNkIDwtIGJhdHNbYyhpZC5pLCBpZC5qKV0KICAgIHNkIDwtIGRjYXN0KHNkLCBlY290eXBlIH4gaWQsIHZhbHVlLnZhciA9ICJyZWwuYWJ1bmQiLCAKICAgICAgICAgICAgICAgIGZ1bi5hZ2dyZWdhdGUgPSBtZWFuKQogICAgc2QgPC0gYXMubWF0cml4KHNkWywgLTFdKQogICAgZ2VuSlNEKHNkKQogIH0KICB9LCBieSA9IC4oaWQuaSwgaWQuaildCnJlYyA8LSBiYXRzLmRpdltpZC5pICE9IGlkLmpdCnNldG5hbWVzKHJlYywgbmFtZXMocmVjKSwgc2FwcGx5KG5hbWVzKHJlYyksIGZ1bmN0aW9uKHN0cikgewogIGlmIChncmVwbCgiXFwuaSIsIHN0cikpIHN1YigiXFwuaSIsICJcXC5qIiwgc3RyKQogIGVsc2UgaWYgKGdyZXBsKCJcXC5qIiwgc3RyKSkgc3ViKCJcXC5qIiwgIlxcLmkiLCBzdHIpCiAgZWxzZSBzdHIKfSkpCmJhdHMuZGl2IDwtIHJiaW5kKGJhdHMuZGl2LCByZWMpCmJhdHMuZGl2WywgZGlzdGFuY2UgOj0gc3FydChqc2QpXQpiYXRzLmRpdlssICI6PSIgKG1vbnRoLmkgPSBhcy5udW1lcmljKG1vbnRoLmkpLCAKICAgICAgICAgICAgICAgICBtb250aC5qID0gYXMubnVtZXJpYyhtb250aC5qKSldCmJhdHMuZGl2WywgZGVsdGEgOj0gbW9udGguaiAtIG1vbnRoLmldCmBgYApgYGB7ciBiYXRzLWpzZC1tZHN9CnZlcnRpY2VzIDwtIHVuaXF1ZShiYXRzWywgLihpZCwgbW9udGgsIGNhbC5tb250aCwgZGVwdGgpXSkKZWRnZXMgPC0gYmF0cy5kaXZbZGVsdGEgPT0gMSwgLihpZC5pLCBpZC5qLCBkZXB0aCA9IGFzLm51bWVyaWMoZGVwdGgpKV0KZ3JhcGggPC0gZ3JhcGhfZnJvbV9kYXRhX2ZyYW1lKGVkZ2VzLCBkaXJlY3RlZCA9IEZBTFNFLCB2ZXJ0aWNlcykKYmF0cy5kZXB0aHMgPC0gdW5pcXVlKGJhdHMkZGVwdGgpCmJhdHMuZGVwdGhzIDwtIGJhdHMuZGVwdGhzW29yZGVyKGFzLm51bWVyaWMoYmF0cy5kZXB0aHMpKV0KbmFtZXMoYmF0cy5kZXB0aHMpIDwtIGJhdHMuZGVwdGhzCmJhdHMuZG1zIDwtIGxhcHBseShiYXRzLmRlcHRocywgZnVuY3Rpb24oZGUpIHsKICBkIDwtIGJhdHMuZGl2W2RlcHRoID09IGRlXQogIE1ha2VEaXN0TWF0cml4KGQsICJpZC5pIiwgImlkLmoiKQp9KQpmaXRzIDwtIGxhcHBseShiYXRzLmRtcywgZnVuY3Rpb24oZG0pIHsKICBDb29yZENNRFMoZG0pCn0pCnhmb3JtcyA8LSBsYXBwbHkoZml0cywgZnVuY3Rpb24oeCkgewogIHgkcG9pbnRzCn0pICU+JSByYmluZGxpc3QodXNlLm5hbWVzID0gVFJVRSwgaWRjb2wgPSAiZGVwdGgiKQplaWdyYW5rcyA8LSBsYXBwbHkoZml0cywgZnVuY3Rpb24oeCkgewogIHgkZWlncmFuawp9KSAlPiUgcmJpbmRsaXN0KHVzZS5uYW1lcyA9IFRSVUUsIGlkY29sID0gImRlcHRoIikKZWlncmFua3NbLCBkZXB0aCA6PSBmYWN0b3IoZGVwdGgsIGxldmVscyA9IGJhdHMuZGVwdGhzKV0KYGBgCmBgYHtyIGJhdHMtcGF0aC1wbG90cyxmaWcud2lkdGg9NyxmaWcuaGVpZ2h0PTl9CnNldGtleSh4Zm9ybXMsIHNhbXBsZSkKbG8gPC0gY3JlYXRlX2xheW91dChncmFwaCwgIm1hbnVhbCIsIG5vZGUucG9zaXRpb25zID0geGZvcm1zW1YoZ3JhcGgpJG5hbWVdKQptYnJlYWtzIDwtIGMoMSwgMywgNiwgOSwgMTIpICMgSmFuLCBwbHVzIG1vbnRocyBvZiBzb2xzdGljZXMgKyBlcXVpbm94ZXMKZ2dyYXBoKGxvKSArCiAgZ2VvbV9lZGdlX2xpbmsoYXJyb3cgPSBhcnJvdyh0eXBlID0gImNsb3NlZCIsIGxlbmd0aCA9IHVuaXQoMywgInBvaW50cyIpKSwKICAgICAgICAgICAgICAgICBlbmRfY2FwID0gc3F1YXJlKGxlbmd0aCA9IDMsIHVuaXQgPSAicG9pbnRzIiksCiAgICAgICAgICAgICAgICAgZWRnZV93aWR0aCA9IDAuMikgKwogIGdlb21fbm9kZV9wb2ludChhZXMoY29sb3IgPSBjYWwubW9udGgpLCBzaXplID0gMC41KSArCiAgc2NhbGVfY29sb3JfZ3JhZGllbnRuKHZhbHVlcyA9IHNjYWxlczo6cmVzY2FsZShtYnJlYWtzKSwKICAgICAgICAgICAgICAgICAgICAgICAgY29sb3JzID0gYygiYmx1ZSIsICJncmVlbjQiLCAieWVsbG93IiwgIm9yYW5nZSIsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgImJsdWUiKQogICAgICAgICAgICAgICAgICAgICAgICApICsKICBmYWNldF93cmFwKH4gZGVwdGgsIG5jb2wgPSAzKSArCiAgdGhlbWVfZ3JhcGgoYmFzZV9mYW1pbHkgPSAiSGVsdmV0aWNhIikgKwogIHRoZW1lKGFzcGVjdC5yYXRpbyA9IDEpCmBgYAoKVGhpcyBhbHNvIHNob3dzIHRoYXQgc2Vhc29uYWwgY3ljbGluZyBpcyBtb3JlIHJlcHJvZHVjaWJsZSBhdCBzb21lIGRlcHRocy4KRm9yIGRlcHRocyBzaGFsbG93ZXIgdGhhbiAxMDAsIHRoZXJlIHNlZW1zIHRvIGJlIGEgcmVwcm9kdWNpYmxlIHBhdGgsIGFuZCB0aGUgY29tcG9zaXRpb24gc2VlbXMgdG8gY2hhbmdlIG1vcmUgZ3JhZHVhbGx5LCBhcyBjYW4gYmUgc2VlbiBpbiB0aGUgY2xvc2Ugc3BhY2luZyBvZiBtb3N0IGNvbnNlY3V0aXZlIHRpbWVwb2ludHMuCkZvciBkZXB0aHMgMTIwLTE2MCwgdGhlcmUgYXJlIGFsc28gcmVwcm9kdWNpYmxlIHBhdGhzLCBob3dldmVyLCB0aGVyZSBhcmUgMyBjbHVzdGVycyBvZiB0aW1lIHBvaW50cyAoc2VlbWluZ2x5IHJlcHJlc2VudGluZyBzcHJpbmcsIHN1bW1lci9lYXJseSBmYWxsLCBhbmQgbGF0ZSBmYWxsL3dpbnRlcikgd2l0aCBsYXJnZSBnYXBzIGJldHdlZW4gdGhlbSwgYW5kIHRoZSBsb25nIGxlYXBzIGJldHdlZW4gY2x1c3RlcnMgc3VnZ2VzdHMgdGhlIHNlYXNvbmFsIGNvbXBvc2l0aW9uYWwgdHJhbnNpdGlvbnMgYXJlIG1vcmUgZHJhc3RpYy4KRmluYWxseSwgZGVwdGhzIDE4MC0yMDAgYXBwZWFyIG1vcmUgcmFuZG9tLgoKRWlnZW52YWx1ZXMgb2YgTURTIHNob3cgdGhhdCB0aGlzIHRyYW5zZm9ybWF0aW9uIGNhcHR1cmVzIG1vc3Qgb2YgdGhlIGluZm9ybWF0aW9uOgpgYGB7cixiYXRzLWpzZC1laWd9CmdncGxvdChlaWdyYW5rcywgYWVzKHggPSByYW5rLCB5ID0gdmFsdWUgXjIpKSArCiAgZ2VvbV9wb2ludCgpICsKICBzY2FsZV94X2xvZzEwKCkgKwogIGZhY2V0X3dyYXAofiBkZXB0aCwgc2NhbGVzID0gImZyZWVfeSIpCmBgYAoKSGVhdG1hcHBpbmcgdGhlIEpTRHMgc2hvd3Mgb2NjdXBhbmN5IG9mIHN0YWJsZSBzdGF0ZXMgYXMgZGFyayBzcXVhcmVzIG9mIGhpZ2ggdGVtcG9yYWwgc2ltaWxhcml0eSBhbG9uZyB0aGUgZGlhZ29uYWwuClJlY3VycmVuY2Ugb2Ygc3RhYmxlIHN0YXRlcyBzaG93IGFzIGRhcmsgb2ZmLWRpYWdvbmFsIHJlY3RhbmdsZXMuCkl0IGlzIGNsZWFyIHRoZSB0aW1lIHNjYWxlcyBvZiBzdGFiaWxpdHkgKHNpemVzIG9mIG9uLWRpYWdvbmFsIGRhcmsgc3F1YXJlcykgYXJlIGRpZmZlcmVudCBmb3IgZGVwdGhzIDEtNDAgYW5kIDEwMC0xNjAuCjYwLTgwIHNlZW0gdG8gYmUgYSBoeWJyaWQgb2YgdGhlIHR3byByZWdpbWVzLCBhbmQgMTgwLTIwMCBzZWVtIHRvIGdvIHRvd2FyZCByYW5kb21uZXNzLgpgYGB7ciBiYXRzLXRpbGUsZmlnLmFzcD0xLjV9CmJhdHMuZGl2WywgZGVwdGggOj0gYXMubnVtZXJpYyhkZXB0aCldCmdncGxvdChiYXRzLmRpdiwgYWVzKHggPSBtb250aC5pLCB5ID0gbW9udGguaikpICsKICBnZW9tX3RpbGUoYWVzKGZpbGwgPSBqc2QpKSArIAogIGZhY2V0X3dyYXAofiBkZXB0aCwgbmNvbCA9IDMpICsgCiAgdGhlbWUoYXNwZWN0LnJhdGlvID0gMSkKYGBgCgpEYXZpZC1zdHlsZSwgSlNELWJhc2VkICdhdXRvY29ycmVsYXRpb24uJwpUaGUgcGVyaW9kaWNpdHkgb2YgbWFueSBvZiB0aGUgYXV0b2NvcnJlbGF0aW9uIGZ1bmN0aW9ucyBzaG93cyBzdHJvbmcgcGVyaW9kaWMgZHluYW1pY3MgYXQgYSBzaW5nbGUgdGltZSBzY2FsZS4KYGBge3IgYmF0cy1hdXRvY29ycixmaWcuYXNwPTF9CmdncGxvdChiYXRzLmRpdltkZWx0YSA+IDBdLCBhZXMoeCA9IGRlbHRhLCB5ID0ganNkKSkgKwogIGdlb21fcG9pbnQoc2l6ZSA9IDAuMikgKwogIGdlb21fc21vb3RoKCkgKwogIGZhY2V0X3dyYXAofiBkZXB0aCwgbmNvbCA9IDMpIApgYGAKIyMgSE9UCmBgYHtyIGhvdHMtdHMsZmlnLmFzcD0xfQpob3RbLCByZWwuYWJ1bmQgOj0gYWJ1bmRhbmNlIC8gc3VtKGFidW5kYW5jZSksIGJ5ID0gZGVwdGhdCmhvdFssIGxvZy5yZWwuYWJ1bmQgOj0gbG9nMTAocmVsLmFidW5kKV0KZ2dwbG90KGhvdCwgYWVzKHggPSBtb250aCwgeSA9IGxvZy5yZWwuYWJ1bmQpKSArCiAgZ2VvbV9wYXRoKGFlcyhncm91cCA9IGVjb3R5cGUpKSArCiAgZmFjZXRfZ3JpZChkZXB0aCB+IGVjb3R5cGUpICsKICB0aGVtZShheGlzLnRleHQueCA9IGVsZW1lbnRfdGV4dChhbmdsZSA9IDkwLCB2anVzdCA9IDAuNSwgaGp1c3QgPSAxKSkKYGBgCmBgYHtyfQpzZXRrZXkoaG90LCBtb250aCkKIyBhbGwgcGFpcnMKaG90WywgaWQgOj0gcGFzdGUobW9udGgsIGRlcHRoLCBzZXAgPSAiXyIpXQpob3QuaWRzIDwtIHVuaXF1ZShob3QkaWQpCmhvdC5kaXYgPC0gTWFrZU5vblJlZHVuZGFudFBhaXJzKGhvdC5pZHMsIHByZWZpeCA9ICJpZCIpCmhvdC5kaXZbLCBjKCJtb250aC5pIiwgImRlcHRoLmkiKSA6PSB0c3Ryc3BsaXQoaWQuaSwgIl8iKV0KaG90LmRpdlssIGMoIm1vbnRoLmoiLCAiZGVwdGguaiIpIDo9IHRzdHJzcGxpdChpZC5qLCAiXyIpXQojIGl0IHdvdWxkIGJlIG5pY2UgdG8gZ2V0IGRpc3RhbmNlcyBiZXR3ZWVuIGRlcHRocyBidXQgd2UnbGwgZG8gc2FtZSBkZXB0aCBybgojIGRvd24gYnkgb3JkZXIgb2YgbWFnbml0dWRlCmhvdC5kaXYgPC0gaG90LmRpdltkZXB0aC5pID09IGRlcHRoLmogJiBtb250aC5qID49IG1vbnRoLmldCmhvdC5kaXZbLCBkZXB0aC5qIDo9IE5VTExdCnNldG5hbWVzKGhvdC5kaXYsICJkZXB0aC5pIiwgImRlcHRoIikKc2V0a2V5KGhvdCwgaWQpCmhvdC5kaXZbLCBqc2QgOj0gewogIGlmIChpZC5pID09IGlkLmopIHsKICAgIDAKICB9IGVsc2UgewogICAgc2QgPC0gaG90W2MoaWQuaSwgaWQuaildCiAgICBzZCA8LSBkY2FzdChzZCwgZWNvdHlwZSB+IGlkLCB2YWx1ZS52YXIgPSAicmVsLmFidW5kIiwgCiAgICAgICAgICAgICAgICBmdW4uYWdncmVnYXRlID0gbWVhbikKICAgIHNkIDwtIGFzLm1hdHJpeChzZFssIC0xXSkKICAgIGdlbkpTRChzZCkKICB9CiAgfSwgYnkgPSAuKGlkLmksIGlkLmopXQpyZWMgPC0gaG90LmRpdltpZC5pICE9IGlkLmpdCnNldG5hbWVzKHJlYywgbmFtZXMocmVjKSwgc2FwcGx5KG5hbWVzKHJlYyksIGZ1bmN0aW9uKHN0cikgewogIGlmIChncmVwbCgiXFwuaSIsIHN0cikpIHN1YigiXFwuaSIsICJcXC5qIiwgc3RyKQogIGVsc2UgaWYgKGdyZXBsKCJcXC5qIiwgc3RyKSkgc3ViKCJcXC5qIiwgIlxcLmkiLCBzdHIpCiAgZWxzZSBzdHIKfSkpCmhvdC5kaXYgPC0gcmJpbmQoaG90LmRpdiwgcmVjKQpob3QuZGl2WywgZGlzdGFuY2UgOj0gc3FydChqc2QpXQpob3QuZGl2WywgIjo9IiAobW9udGguaSA9IGFzLm51bWVyaWMobW9udGguaSksIAogICAgICAgICAgICAgICAgIG1vbnRoLmogPSBhcy5udW1lcmljKG1vbnRoLmopKV0KaG90LmRpdlssIGRlbHRhIDo9IG1vbnRoLmogLSBtb250aC5pXQpgYGAKClNoYWxsb3dlciBkZXB0aHMgYXJlIG1vcmUgc3RhYmxlIGluIGNvbXBvc2l0aW9uOgpgYGB7cn0KZ2dwbG90KGhvdC5kaXYsIGFlcyh4ID0gZGlzdGFuY2UpKSArCiAgc3RhdF9lY2RmKGFlcyhjb2xvciA9IGZhY3RvcihkZXB0aCwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGxldmVscyA9IGFzLmNoYXJhY3RlcigKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgc29ydCgKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB1bmlxdWUoCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBhcy5udW1lcmljKGRlcHRoKQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgKQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICkKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgKQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgKQogICkpICsKICBsYWJzKGNvbG9yID0gImRlcHRoIikKYGBgCgpgYGB7cn0KdmVydGljZXMgPC0gdW5pcXVlKGhvdFssIC4oaWQsIG1vbnRoLCBjYWwubW9udGgsIGRlcHRoKV0pCmVkZ2VzIDwtIGhvdC5kaXZbZGVsdGEgPT0gMSwgLihpZC5pLCBpZC5qLCBkZXB0aCA9IGFzLm51bWVyaWMoZGVwdGgpKV0KZ3JhcGggPC0gZ3JhcGhfZnJvbV9kYXRhX2ZyYW1lKGVkZ2VzLCBkaXJlY3RlZCA9IEZBTFNFLCB2ZXJ0aWNlcykKaG90LmRlcHRocyA8LSB1bmlxdWUoaG90JGRlcHRoKQpob3QuZGVwdGhzIDwtIGhvdC5kZXB0aHNbb3JkZXIoYXMubnVtZXJpYyhob3QuZGVwdGhzKSldCm5hbWVzKGhvdC5kZXB0aHMpIDwtIGhvdC5kZXB0aHMKaG90LmRtcyA8LSBsYXBwbHkoaG90LmRlcHRocywgZnVuY3Rpb24oZGUpIHsKICBkIDwtIGhvdC5kaXZbZGVwdGggPT0gZGVdCiAgTWFrZURpc3RNYXRyaXgoZCwgImlkLmkiLCAiaWQuaiIpCn0pCmZpdHMgPC0gbGFwcGx5KGhvdC5kbXMsIGZ1bmN0aW9uKGRtKSB7CiAgQ29vcmRDTURTKGRtKQp9KQp4Zm9ybXMgPC0gbGFwcGx5KGZpdHMsIGZ1bmN0aW9uKHgpIHsKICB4JHBvaW50cwp9KSAlPiUgcmJpbmRsaXN0KHVzZS5uYW1lcyA9IFRSVUUsIGlkY29sID0gImRlcHRoIikKaG90LmVpZ3JhbmtzIDwtIGxhcHBseShmaXRzLCBmdW5jdGlvbih4KSB7CiAgeCRlaWdyYW5rCn0pICU+JSByYmluZGxpc3QodXNlLm5hbWVzID0gVFJVRSwgaWRjb2wgPSAiZGVwdGgiKQpnZ3Bsb3QoaG90LmVpZ3JhbmtzLCBhZXMoeCA9IHJhbmssIHkgPSB2YWx1ZSBeIDIpKSArCiAgZ2VvbV9wb2ludCgpICsKICBmYWNldF93cmFwKH4gYXMubnVtZXJpYyhkZXB0aCksIHNjYWxlcyA9ICJmcmVlX3kiKQpgYGAKCmBgYHtyIGhvdC1wYXRoLXBsb3RzLGZpZy5hc3A9MS4yfQpzZXRrZXkoeGZvcm1zLCBzYW1wbGUpCmxvIDwtIGNyZWF0ZV9sYXlvdXQoZ3JhcGgsICJtYW51YWwiLCBub2RlLnBvc2l0aW9ucyA9IHhmb3Jtc1tWKGdyYXBoKSRuYW1lXSkKbWJyZWFrcyA8LSBjKDEsIDMsIDYsIDksIDEyKSAjIEphbiwgcGx1cyBtb250aHMgb2Ygc29sc3RpY2VzICsgZXF1aW5veGVzCmdncmFwaChsbykgKwogIGdlb21fZWRnZV9saW5rKGFycm93ID0gYXJyb3codHlwZSA9ICJjbG9zZWQiLCBsZW5ndGggPSB1bml0KDMsICJwb2ludHMiKSksCiAgICAgICAgICAgICAgICAgZW5kX2NhcCA9IHNxdWFyZShsZW5ndGggPSAzLCB1bml0ID0gInBvaW50cyIpLAogICAgICAgICAgICAgICAgIGVkZ2Vfd2lkdGggPSAwLjIpICsKICBnZW9tX25vZGVfcG9pbnQoYWVzKGNvbG9yID0gY2FsLm1vbnRoKSwgc2l6ZSA9IDAuNSkgKwogIHNjYWxlX2NvbG9yX2dyYWRpZW50bih2YWx1ZXMgPSBzY2FsZXM6OnJlc2NhbGUobWJyZWFrcyksCiAgICAgICAgICAgICAgICAgICAgICAgIGNvbG9ycyA9IGMoImJsdWUiLCAiZ3JlZW40IiwgInllbGxvdyIsICJvcmFuZ2UiLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICJibHVlIikKICAgICAgICAgICAgICAgICAgICAgICAgKSArCiAgZmFjZXRfd3JhcCh+IGRlcHRoLCBuY29sID0gMykgKwogIHRoZW1lX2dyYXBoKGJhc2VfZmFtaWx5ID0gIkhlbHZldGljYSIpICsKICB0aGVtZShhc3BlY3QucmF0aW8gPSAxKQpgYGAKYGBge3IsIGZpZy5hc3A9MS41fQpob3QuZGl2WywgZGVwdGggOj0gYXMubnVtZXJpYyhhcy5jaGFyYWN0ZXIoZGVwdGgpKV0KZ2dwbG90KGhvdC5kaXYsIGFlcyh4ID0gbW9udGguaSwgeSA9IG1vbnRoLmopKSArCiAgZ2VvbV90aWxlKGFlcyhmaWxsID0ganNkKSkgKyAKICBmYWNldF93cmFwKH4gZGVwdGgsIG5jb2wgPSAzKSArIAogIHRoZW1lKGFzcGVjdC5yYXRpbyA9IDEpCmBgYAoKIyBOYWhhbnQKClRoZXJlIGFyZSB0b28gbWFueSBPVFVzLgpUaGV5IHNob3VsZCBwcm9iYWJseSBiZSBhZ2dyZWdhdGVkIHNvbWVob3cuCkhlcmUgd2UgYWdncmVnYXRlIGFsbCByZWFkcyB0aGF0IG1hcCB0byB0aGUgc2FtZSBwaHlsdW0sIHdoaWNoIHJlc3VsdHMgaW4gYSBtYW5hZ2VhYmxlIG51bWJlciBvZiB2YXJpYWJsZXMuCkJ1dCBvbmUgY291bGQganVzdCBhcyB3ZWxsIGFnZ3JlZ2F0ZSBhdCBhbnkgb3RoZXIgdGF4b25vbWljIGxldmVsIG9yIG5vdCBhdCBhbGwuCmBgYHtyfQpuYWhhbnQuYmFjIDwtIGZyZWFkKHBhc3RlMChkYXRhLmRpciwgIkJhY3ROb3JtLnR4dCIpLCBoZWFkZXIgPSBUUlVFKQpuYWhhbnQuYmFjIDwtIG1lbHQobmFoYW50LmJhYywgaWQudmFycyA9IGMoIk9UVSIsICJDb25zZW5zdXNMaW5lYWdlIiksIAogICAgICAgICAgICAgICAgICAgdmFyaWFibGUubmFtZSA9ICJkYXkiKQpuYWhhbnQuYmFjIDwtIG5haGFudC5iYWNbLCBkYXkgOj0gYXMubnVtZXJpYyhhcy5jaGFyYWN0ZXIoZGF5KSldCm5haGFudC5iYWMgPC0gbmFoYW50LmJhY1ssIHZhbHVlIDo9IGFzLm51bWVyaWModmFsdWUpXQojIG1lcmdlIE9UVSBjb3VudHMgYnkgY29uc2Vuc3VzIGxpbmVhZ2UKbmFoYW50LmJhYyA8LSBuYWhhbnQuYmFjWywgLihmcmVxID0gc3VtKHZhbHVlKSksIGJ5ID0gLihDb25zZW5zdXNMaW5lYWdlLCBkYXkpXQojIHBhcnNlIGxpbmVhZ2UKIyBub3RoaW5nIGlzIG1hcHBlZCB0byBzcGVjaWVzIHJlc29sdXRpb24KbmFoYW50LmJhYyA8LSBuYWhhbnQuYmFjWywgQ29uc2Vuc3VzTGluZWFnZSA6PSBnc3ViKCI7IiwgIiIsIENvbnNlbnN1c0xpbmVhZ2UpXQpuYWhhbnQuYmFjIDwtIG5haGFudC5iYWNbLCBjKCJmb28iLCAia2luZ2RvbSIsICJwaHlsdW0iLCAiY2xhc3MiLCAib3JkZXIiLCAiZmFtaWx5IiwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAiZ2VudXMiKSA6PSB0c3Ryc3BsaXQoQ29uc2Vuc3VzTGluZWFnZSwgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICJbWzphbHBoYTpdXV9fIildCm5haGFudC5iYWMgPC0gbmFoYW50LmJhY1ssIGZvbyA6PSBOVUxMXQojIHRoZXJlIGFyZSB3YXkgdG9vIG1hbnkgY2xhc3NlcyBhbmQgZmluZXIsIHBsb3QgdGltZSBzZXJpZXMgb2YgcGh5bGEKcGh5bGEgPC0gbmFoYW50LmJhY1traW5nZG9tICE9ICIiICYgcGh5bHVtICE9ICIiLCAuKGZyZXEgPSBzdW0oZnJlcSkpLCAKICAgICAgICAgICBieSA9IC4oZGF5LCBwaHlsdW0pXSAKYGBgCmBgYHtyIG5haGFudC10cywgZmlnLmFzcD0xfQpwaHlsYSAlPiUgCiAgZ3JvdXBfYnkocGh5bHVtKSAlPiUgCiAgbXV0YXRlKGZyZXEgPSBzY2FsZXM6OnJlc2NhbGUoZnJlcSkpICU+JSAKICBnZ3Bsb3QoYWVzKHggPSBhcy5udW1lcmljKGRheSksIHkgPSBmcmVxKSkgKwogIHRoZW1lKHN0cmlwLnRleHQgPSBlbGVtZW50X3RleHQoc2l6ZSA9IDEwKSwKICAgICAgICBheGlzLnRleHQueCA9IGVsZW1lbnRfdGV4dChhbmdsZSA9IDkwLCB2anVzdCA9IDAuNSwgaGp1c3QgPSAxKQogICAgICAgICkgKwogIHNjYWxlX3lfY29udGludW91cyhicmVha3MgPSBjKDAsIDAuNSwgMSkpICsKICBnZW9tX2xpbmUoYWVzKGdyb3VwID0gcGh5bHVtKSkgKwogIGZhY2V0X3dyYXAofiBwaHlsdW0sIG5jb2wgPSA0KSArCiAgbGFicyh5ID0gImZyZXF1ZW5jeSAobm9ybWFsaXplZCkiKQpgYGAKCldlIGNhbiBsb29rIGF0IHRoZSBzcGVjdHJhbCBkZW5zaXR5IG9mIHRoZSBwaHlsYSB0aW1lIHNlcmllcy4KUGh5bGEgd2l0aCBwZWFrcyBpbiB0aGUgbG93IGZyZXF1ZW5jaWVzIGV4aGliaXQgc2xvdyBmbHVjdHVhdGlvbnMuCkl0IHNlZW1zIHRoZXJlIHJlYWxseSBhcmUgc2xvdyBhbmQgYnJvYWQtc3BlY3RydW0gdGF4YSBhdCB0aGlzIGxldmVsLgpgYGB7ciBuYWhhbnQtcGh5bGEtc3BlY3RyYX0KcGh5bGEuc3BlYyA8LSBwaHlsYSAlPiUKICBkY2FzdChkYXkgfiBwaHlsdW0sIHZhbHVlLnZhciA9ICJmcmVxIikgJT4lIAogIHNlbGVjdCgtZGF5KSAlPiUgCiAgc3RhdHM6OnNwZWN0cnVtKHBsb3QgPSBGQUxTRSkKcGh5bGEuc3BlYyA8LSBkYXRhLnRhYmxlKGNiaW5kKHBoeWxhLnNwZWMkZnJlcSwgcGh5bGEuc3BlYyRzcGVjKSkgJT4lIAogIHNldG5hbWVzKGMoImZyZXEiLCBwaHlsYS5zcGVjJHNuYW1lcykpICU+JSAKICBtZWx0KGlkLnZhcnMgPSAiZnJlcSIsIHZhcmlhYmxlLm5hbWUgPSAicGh5bHVtIikKcGh5bGEuc3BlYyAlPiUgCiAgZ3JvdXBfYnkocGh5bHVtKSAlPiUgCiAgbXV0YXRlKHZhbHVlID0gdmFsdWUgLyBzdW0odmFsdWUpKSAlPiUgCiAgZ2dwbG90KGFlcyh4ID0gZnJlcSwgeSA9IHBoeWx1bSkpICsKICBsYWJzKHggPSAiZnJlcXVlbmN5ICgxL2RheSkiKSArCiAgZ2VvbV90aWxlKGFlcyhmaWxsID0gdmFsdWUpKSAKYGBgCgojIFIgdGhlcmUgc3RhdGV6PwoKQXJlIHRoZXJlIHF1YWxpdGF0aXZlIGNvYXJzZS1ncmFpbmFibGUgY29tcG9zaXRpb25hbCBzdGF0ZXMgaW4gdGhlIE5haGFudCBkYXRhPwpgYGB7ciBuYWhhbnQtY29tcG9zaXRpb24tY2x1c3RlcmluZ30KcGh5bGFbLCBkYXkgOj0gYXMuY2hhcmFjdGVyKGRheSldCmRheXMgPC0gdW5pcXVlKHBoeWxhWywgZGF5XSkKZGF5LmRpdiA8LSBkYXRhLnRhYmxlKGV4cGFuZC5ncmlkKGRheS5pID0gZGF5cywgZGF5LmogPSBkYXlzKSkKZGF5LmRpdlssICI6PSIgKGRheS5pID0gYXMuY2hhcmFjdGVyKGRheS5pKSwgCiAgICAgICAgICAgICAgICAgICAgICAgICAgIGRheS5qID0gYXMuY2hhcmFjdGVyKGRheS5qKSldCnNldGtleShwaHlsYSwgZGF5KQpkYXkuZGl2WywganNkIDo9IHsKICBpZiAoZGF5LmkgPT0gZGF5LmopIHsKICAgIDAKICB9IGVsc2UgewogICAgc2QgPC0gcGh5bGFbYyhkYXkuaSwgZGF5LmopXQogICAgc2QgPC0gZGNhc3Qoc2QsIHBoeWx1bSB+IGRheSwgdmFsdWUudmFyID0gImZyZXEiKQogICAgbSA8LSBhcy5tYXRyaXgoc2RbLCAyOjNdKQogICAgZCA8LSBnZW5KU0QobSkKICAgIGQKICB9Cn0sIGJ5ID0gLihkYXkuaSwgZGF5LmopXQpkYXkuZGl2WywgZGlzdGFuY2UgOj0gc3FydChqc2QpXQpgYGAKCkxheW91dCB0aGUgc2FtcGxlcyBieSBKZW5zZW4tU2hhbm5vbiBkaXN0YW5jZSB1c2luZyBgbWRzYCBhbGdvcml0aG0uCkNvbG9yIGJ5IGRheSBzbyBhcyB0byBzZWUgdGVtcG9yYWwgcHJvZ3Jlc3Npb24uCkhpZXJhcmNoaWNhbGx5IGNsdXN0ZXIgYnkgSlMgZGlzdGFuY2UuCgpgYGB7ciBuYWhhbnQtY29tcG9zaXRpb24tY2x1c3RlcmluZy1wbG90LCBmaWcuaGVpZ2h0PTcsIGZpZy53aWR0aD03fQplZGdlcyA8LSBjYmluZChkYXlzWy1sZW5ndGgoZGF5cyldLCBkYXlzWy0xXSkKZ3JhcGggPC0gZ3JhcGhfZnJvbV9kYXRhX2ZyYW1lKGVkZ2VzLCBkaXJlY3RlZCA9IEZBTFNFLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgdmVydGljZXMgPSBkYXRhLnRhYmxlKGlkID0gZGF5cywKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBkYXkgPSBhcy5udW1lcmljKGRheXMpKSkKZG0gPC0gTWFrZURpc3RNYXRyaXgoZGF5LmRpdiwgImRheS5pIiwgImRheS5qIikKZml0IDwtIENvb3JkQ01EUyhkbSkKeGZvcm0gPC0gZml0JHBvaW50cwojIG9yZGVyCnNldGtleSh4Zm9ybSwgc2FtcGxlKQp4Zm9ybSA8LSB4Zm9ybVtWKGdyYXBoKSRuYW1lXQpsYXlvdXQgPC0gY3JlYXRlX2xheW91dChncmFwaCwgIm1hbnVhbCIsIG5vZGUucG9zaXRpb25zID0geGZvcm0pCnAxIDwtIGdncmFwaChsYXlvdXQpICsKICBnZW9tX2VkZ2VfbGluayhhcnJvdyA9IGFycm93KHR5cGUgPSAiY2xvc2VkIiwgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBsZW5ndGggPSB1bml0KDUsICJwb2ludHMiKSksCiAgICAgICAgICAgICAgICAgZWRnZV93aWR0aCA9IDAuMiwKICAgICAgICAgICAgICAgICBlbmRfY2FwID0gc3F1YXJlKGxlbmd0aCA9IDUsIHVuaXQgPSAicG9pbnRzIikKICAgICAgICAgICAgICAgICApICsKICBnZW9tX25vZGVfcG9pbnQoYWVzKGNvbG9yID0gZGF5KSkgKwogIHRoZW1lX2dyYXBoKGJhc2VfZmFtaWx5ID0gIkhlbHZldGljYSIpICsKICBzY2FsZV9jb2xvcl9kaXN0aWxsZXIocGFsZXR0ZSA9ICJTcGVjdHJhbCIpIAojIGNsdXN0ZXJpbmcKaGMgPC0gaGNsdXN0KGRpc3QoZG0pKQpkZW5kcm8gPC0gYXMuZGVuZHJvZ3JhbShoYykKZGVuZHJvIDwtIGRlbmRyYXBwbHkoZGVuZHJvLCBmdW5jdGlvbihkKSB7CiAgaWYgKGlzLmxlYWYoZCkpIHsKICAgIGF0dHIoZCwgIm5vZGVQYXIiKSA8LSBsaXN0KGRheSA9IGFzLm51bWVyaWMoYXR0cihkLCAibGFiZWwiKSkpCiAgfQogIGQKfSkKcDIgPC0gZ2dyYXBoKGRlbmRybywgImRlbmRyb2dyYW0iKSArCiAgZ2VvbV9lZGdlX2VsYm93KCkgKwogICMgZ2VvbV9ub2RlX3RleHQoYWVzKGZpbHRlciA9IGxlYWYsIGNvbG9yID0gZGF5LCBsYWJlbCA9IGRheSksIGFuZ2xlID0gOTAsIHNpemUgPSAyKSArCiAgZ2VvbV9ub2RlX3BvaW50KGFlcyhmaWx0ZXIgPSBsZWFmLCBjb2xvciA9IGRheSkpICsKICBzY2FsZV9jb2xvcl9kaXN0aWxsZXIocGFsZXR0ZSA9ICJTcGVjdHJhbCIpICsKICB0aGVtZV9ncmFwaChiYXNlX2ZhbWlseSA9ICJIZWx2ZXRpY2EiKSAjKwogICMgdGhlbWUoYXNwZWN0LnJhdGlvID0gMSkKcGxvdF9ncmlkKHAxLCBwMiwgbnJvdyA9IDIsIGFsaWduID0gImh2IiwgbGFiZWxzID0gYygiQSIsICJCIikpCmBgYApUaGVzZSBkYXRhIHNob3cgYSBjbGVhciB0cmFuc2l0aW9uIGJldHdlZW4gc3RhYmxlIHN0YXRlcyBhcm91bmQgZGF5IDI0MC4KVGhlc2UgdHdvIHN0YXRlcyBmb3JtIHRoZSB0d28gbWFqb3IgYnJhbmNoZXMgYXQgdGhlIGxvd2VzdCBsZXZlbCBvZiB0aGUgaGllcmFyY2hpY2FsIGNsdXN0ZXJpbmcuCgpUaGUgZWlnZW52YWx1ZXMgb2YgdGhlIE1EUyB0cmFuc2Zvcm0gc2hvdyB0aGF0IGluZm9ybWF0aW9uIGlzIHdlbGwgcHJlc2VydmVkOgpgYGB7ciBiYXRzLW1kcy1laWdlbn0KZ2dwbG90KGZpdCRlaWdyYW5rLCBhZXMoeCA9IHJhbmssIHkgPSB2YWx1ZSBeIDIpKSArCiAgZ2VvbV9wb2ludCgpCmBgYAoKCiMjIFN0YXRpc3RpY3Mgb2YgZHluYW1pY3MgCgpEaXN0cmlidXRpb24gb2YgZGFpbHkgY29tcG9zaXRpb25hbCBzdGVwIHNpemVzLgpUaGUgTWF4d2VsbC1Cb2x0em1hbm4vbG9nbm9ybWFsIHNoYXBlIHRvIHRoZSBkZW5zaXR5IGF0ICRcRGVsdGEodCkgPSAxJCAKc3VnZ2VzdHMgdGhhdCB1bmRlciB0aGlzIHRpbWUgcmVzb2x1dGlvbiB0aGUgY2hhbmdlIGluIGNvbXBvc2l0aW9uIGJlaGF2ZXMKbGlrZSBzb21lIGtpbmQgb2YgcmFuZG9tIHdhbGssIHdpdGggYSBjaGFyYWN0ZXJpc3RpYyBzdGVwIHNpemUgYW5kIHJhcmUgY2hhbmdlcyBvZiBsYXJnZXIgbWFnbml0dWRlLgpgYGB7ciBuYWhhbnQtZGF5LWRlbHRhcywgZmlnLndpZHRoPTcsZmlnLmhlaWdodD02fQpkYXkuZGl2IDwtIGRheS5kaXZbLCBkYXkuZGVsdGEgOj0gYXMubnVtZXJpYyhkYXkuaikgLSBhcy5udW1lcmljKGRheS5pKV0KcDEgPC0gZ2dwbG90KGRheS5kaXZbZGF5LmRlbHRhID09IDEsXSwgYWVzKHggPSBkaXN0YW5jZSkpICsKICBzdGF0X2JpbihiaW5zID0gMzApIApwMiA8LSBnZ3Bsb3QoZGF5LmRpdltkYXkuZGVsdGEgPT0gMV0sIGFlcyh4ID0gYXMubnVtZXJpYyhkYXkuaSksIHkgPSBkaXN0YW5jZSkpICsKICBnZW9tX3BvaW50KCkgKyAKICAjIHN0YXRfc21vb3RoKCkgKyAKICBsYWJzKHggPSAiZGF5IGkiKQpwbG90X2dyaWQocDEsIHAyLCBucm93ID0gMiwgbGFiZWxzID0gIkFVVE8iLCBhbGlnbiA9ICJodiIpCmRheS5kaXZbZGF5LmRlbHRhID4gMF0gJT4lIAogIG11dGF0ZShncm91cCA9IGFzLmZhY3RvcihmbG9vcihkYXkuZGVsdGEgLyAxMCkgKiAxMCksCiAgICAgICAgIGRkZWx0YSA9IGFzLmZhY3RvcihkYXkuZGVsdGEgJSUgMTApKSAlPiUgCiAgZ2dwbG90KGFlcyh4ID0gZGlzdGFuY2UpKSArCiAgc3RhdF9iaW4oYmlucyA9IDMwLCBwb3NpdGlvbiA9ICJpZGVudGl0eSIpICsKICBzY2FsZV9jb2xvcl9icmV3ZXIocGFsZXR0ZSA9ICJTcGVjdHJhbCIpICsKICB0aGVtZShheGlzLnRleHQueCA9IGVsZW1lbnRfdGV4dChhbmdsZSA9IDkwLCB2anVzdCA9IDAuNSwgaGp1c3QgPSAxLCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBzaXplID0gNwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICksCiAgICAgICAgYXhpcy50ZXh0LnkgPSBlbGVtZW50X3RleHQoc2l6ZSA9IDYpCiAgICAgICAgKSArCiAgZmFjZXRfZ3JpZChncm91cCB+IGRkZWx0YSwgc2NhbGVzID0gImZyZWVfeSIpCmBgYAoKQ29tcG9zaXRpb25hbCBkaXN0YW5jZSBhcyBmdW5jdGlvbiBvZiBpbnRlcnZhbC4KVGhpcyBpcyBzb3J0IG9mIGFuIGF1dG9jb3JyZWxhdGlvbiBzcGVjdHJ1bS4KVGhlcmUgYXJlIG5vIHBlYWtzIGluIHRoaXMgJ3NwZWN0cnVtJyBzdWdnZXN0aW5nIHRoZXJlIGFyZSBubyBjaGFyYWN0ZXJpc3RpYwp0aW1lIHNjYWxlcyBvZiBwZXJpb2RpYyBiZWhhdmlvci4KU2luY2UgdGhlcmUgaXMgb25seSBvbmUgbWFqb3Igc3RhdGUgdHJhbnNpdGlvbiBpbiB0aGVzZSBkYXRhLCBpdCBjb3VsZCBhbHNvIGJlIGludGVycHJldGVkIGFzIHRoZSBwZXJpb2Qgb2Ygc3RhdGUgdHJhbnNpdGlvbnMgYmVpbmcgbG9uZ2VyIHRoYW4gdGhlIG9ic2VydmF0aW9uIHRpbWUsIHdoZW4gaW50ZXJwcmV0ZWQgYXMgcGVyaW9kaWMuCmBgYHtyIG5haGFudC1zaW0taW50ZXJ2YWwsIGZpZy53aWR0aD03LCBmaWcuaGVpZ2h0PTV9CmJyIDwtIGRheXNbc2VxKDEsIGxlbmd0aChkYXlzKSwgYnkgPSA1KV0KZ2dwbG90KGRheS5kaXYsIGFlcyh4ID0gZGF5LmksIHkgPSBkYXkuaikpICsKICBnZW9tX3RpbGUoYWVzKGZpbGwgPSBkaXN0YW5jZSkpICsKICBzY2FsZV94X2Rpc2NyZXRlKGJyZWFrcyA9IGJyKSArCiAgc2NhbGVfeV9kaXNjcmV0ZShicmVha3MgPSBicikgKwogIHRoZW1lKGFzcGVjdC5yYXRpbyA9IDEsCiAgICAgICAgYXhpcy50ZXh0LnggPSBlbGVtZW50X3RleHQoYW5nbGUgPSA5MCwgdmp1c3QgPSAwLjUsIGhqdXN0ID0gMSkpCnRsIDwtIGRheS5kaXZbZGF5LmRlbHRhID4gMCwgLihtbi5kaXN0ID0gbWVhbihkaXN0YW5jZSkpLCBieSA9IGRheS5kZWx0YV0KcDAgPC0gZ2dwbG90KGRheS5kaXZbZGF5LmRlbHRhID4gMF0sIGFlcyh4ID0gZGF5LmRlbHRhLCB5ID0gZGlzdGFuY2UpKSAKcDEgPC0gcDAgKyBnZW9tX3BvaW50KHNpemUgPSAxKSArIAogICMgc3RhdF9zbW9vdGgoYWVzKGxpbmV0eXBlID0gIm1lYW4iKSkgICsKICBnZW9tX2xpbmUoYWVzKHkgPSBtbi5kaXN0LCBsaW5ldHlwZSA9ICJtZWFuIiksIHRsLCBjb2xvciA9ICJibHVlIiwgc2l6ZSA9IDIpICsKICBsYWJzKGxpbmV0eXBlID0gIiIsIHggPSAiaW50ZXJ2YWwgKGRheXMpIikKcDIgPC0gcDAgKyBzdGF0X2Jpbl8yZChiaW53aWR0aCA9IGMoMSwgMC4wMSkpICsgbGFicyh4ID0gImludGVydmFsIChkYXlzKSIpCnBsb3RfZ3JpZChwMSwgcDIsIG5yb3cgPSAyLCBhbGlnbiA9ICJodiIsIGxhYmVscyA9ICJBVVRPIikKYGBgCgojIEh1bWFuCgojIyBEYXZpZCBldCBhbApgYGB7cixtZXNzYWdlPUZBTFNFfQpkYXZpZCA8LSBmcmVhZChwYXN0ZTAoZGF0YS5kaXIsICJkYXZpZC9kYXZpZC5vdHVzIiksIAogICAgICAgICAgICAgICBjb2wubmFtZXMgPSBjKCJzYW1wbGUiLCAib3R1IiwgImNvdW50IikKICAgICAgICAgICAgICAgKQojIHBhcnNlIHN1YmplY3QgYW5kIHRpbWVwb2ludHMKZGF2aWQuc2FtcGxlcyA8LSB1bmlxdWUoZGF2aWRbLCAuKHNhbXBsZSldKQpkYXZpZC5zYW1wbGVzWywgYygic3ViamVjdCIsICJkYXkiKSA6PSB0c3Ryc3BsaXQoc2FtcGxlLCAiXyIpXQojIGxvZyB0cmFuc2Zvcm0gb3R1IGNvdW50cwpkYXZpZFssIGxvZy5jb3VudCA6PSBsb2coY291bnQgKyAxKV0KIyBzcGxpdCBieSBzdWJqZWN0CmRhdmlkLnN1YmplY3RzIDwtIHVuaXF1ZShkYXZpZC5zYW1wbGVzJHN1YmplY3QpCm5hbWVzKGRhdmlkLnN1YmplY3RzKSA8LSBkYXZpZC5zdWJqZWN0cwojIGNyZWF0ZSB0YWJsZXMgb2YgZGF5LWRheSBkaXZlcmdlbmNlcwpkYXZpZC5kaXYgPC0gZGF0YS50YWJsZShleHBhbmQuZ3JpZChzYW1wbGUuaSA9IGRhdmlkLnNhbXBsZXMkc2FtcGxlLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBzYW1wbGUuaiA9IGRhdmlkLnNhbXBsZXMkc2FtcGxlKQogICAgICAgICAgICAgICAgICAgICAgICApCmRhdmlkLnNhbXBsZXNbLCBpZHggOj0gMTouTl0KZGF2aWQuc2FtcGxlc1ssIHN1YmouaWR4IDo9IGZyYW5rKGFzLm51bWVyaWMoZGF5KSksIGJ5ID0gc3ViamVjdF0KZGF2aWQuZGl2IDwtIG1lcmdlKGRhdmlkLmRpdiwgZGF2aWQuc2FtcGxlcywgYnkueCA9ICJzYW1wbGUuaSIsIAogICAgICAgICAgICAgICAgICAgYnkueSA9ICJzYW1wbGUiKQpkYXZpZC5kaXYgPC0gbWVyZ2UoZGF2aWQuZGl2LCBkYXZpZC5zYW1wbGVzLCBieS54ID0gInNhbXBsZS5qIiwgCiAgICAgICAgICAgICAgICAgICBieS55ID0gInNhbXBsZSIsIHN1ZmZpeGVzID0gYygiLmkiLCAiLmoiKSkKZGF2aWQuZGl2IDwtIGRhdmlkLmRpdltpZHguaiA+PSBpZHguaV0Kc2V0a2V5KGRhdmlkLCBzYW1wbGUpCmRhdmlkLmRpdlssIGpzZCA6PSB7CiAgaWYgKHNhbXBsZS5pID09IHNhbXBsZS5qKSB7CiAgICAwCiAgfSBlbHNlIHsKICAgIHNkIDwtIGRhdmlkW2Moc2FtcGxlLmksIHNhbXBsZS5qKV0KICAgIG0gPC0gZGNhc3Qoc2QsIG90dSB+IHNhbXBsZSwgdmFsdWUudmFyID0gImNvdW50IikKICAgIG0gPC0gYXMubWF0cml4KG1bLCAyOjNdKQogICAgbVtpcy5uYShtKV0gPC0gMAogICAgZ2VuSlNEKG0pCiAgfQp9LCBieSA9IC4oc2FtcGxlLmksIHNhbXBsZS5qKV0KIyByZWNpcHJvY2FsIGRpc3RhbmNlcwpkYXZpZC5kaXYgPC0gZGF2aWQuZGl2W3NhbXBsZS5pICE9IHNhbXBsZS5qXSAlPiUgCiAgc2V0bmFtZXMobmFtZXMoZGF2aWQuZGl2KSwgc2FwcGx5KG5hbWVzKGRhdmlkLmRpdiksIGZ1bmN0aW9uKHgpIHsKICAgIGlmIChncmVwbCgiaWR4XFwuaSIsIHgpKSB7CiAgICAgIGdzdWIoImlkeFxcLmkiLCAiaWR4XFwuaiIsIHgpCiAgICB9IGVsc2UgaWYgKGdyZXBsKCJpZHhcXC5qIiwgeCkpIHsKICAgICAgZ3N1YigiaWR4XFwuaiIsICJpZHhcXC5pIiwgeCkKICAgIH0gZWxzZSBpZiAoZ3JlcGwoIlxcLmkiLCB4KSkgewogICAgICBnc3ViKCJcXC5pIiwgIlxcLmoiLCB4KQogICAgfSBlbHNlIGlmIChncmVwbCgiXFwuaiIsIHgpKSB7CiAgICAgIGdzdWIoIlxcLmoiLCAiXFwuaSIsIHgpCiAgICB9IGVsc2UgeAogIH0pCiAgKSAlPiUgIAogIHJiaW5kKGRhdmlkLmRpdikKZGF2aWQuZGl2WywgZGlzdGFuY2UgOj0gc3FydChqc2QpXQpkYXZpZC5kaXZbLCBkYXkuZGVsdGEgOj0gYXMubnVtZXJpYyhkYXkuaikgLSBhcy5udW1lcmljKGRheS5pKV0KZGF2aWQuZGl2W3N1YmplY3QuaSA9PSBzdWJqZWN0LmosIGluY3JlbWVudCA6PSBzdWJqLmlkeC5qIC0gc3Viai5pZHguaV0KYGBgCgpNZXJnZSBldmVudCBtZXRhZGF0YToKYGBge3J9CiMgbWV0YWRhdGEKc2V0a2V5KGRhdmlkLnNhbXBsZXMsIHN1YmplY3QpCmV2ZW50cyA8LSBtYXBwbHkoZnVuY3Rpb24oc3RhcnQsIGVuZCwgc3ViamVjdCwgZXZlbnQpIHsKICB4IDwtIGRhdGEudGFibGUoZGF5ID0gc2VxKHN0YXJ0LCBlbmQsIGJ5ID0gMSksIHN1YmplY3QgPSBzdWJqZWN0LCAKICAgICAgICAgICAgICAgICAgZXZlbnQgPSBldmVudCkKICB4Cn0sIHN0YXJ0ID0gYygwLCA3MSwgODAsIDEwNCwgMTIzLCAKICAgICAgICAgICAgIDAsIDE1MSwgMTYwICksCmVuZCA9ICAgYyg3MCwgMTIyLCA4NSwgMTEzLCBkYXZpZC5zYW1wbGVzWyJBIiwgbWF4KGFzLm51bWVyaWMoZGF5KSldLCAKICAgICAgICAgIDE1MCwgMTU5LCBkYXZpZC5zYW1wbGVzWyJCIiwgbWF4KGFzLm51bWVyaWMoZGF5KSldKSwKc3ViamVjdCA9IGMoIkEiLCAiQSIsICJBIiwgIkEiLCAiQSIsIAogICAgICAgICAgICAiQiIsICJCIiwgIkIiKSwKZXZlbnQgPSBjKCJVUyAocHJlKSIsICJ0cmF2ZWwiLCAiZGlhcnJoZWEgMSIsICJkaWFycmhlYSAyIiwgIlVTIChwb3N0KSIsIAogICAgICAgICAgInByZS1TYWxtb25lbGxhIiwgIlNhbG1vbmVsbGEiLCAicG9zdC1TYWxtb25lbGxhIiksClNJTVBMSUZZID0gRkFMU0UpICU+JSByYmluZGxpc3QodXNlLm5hbWVzID0gVFJVRSkgCiMgY29sbGFwc2UgZXZlbnQgbGFiZWxzIHBlciBkYXkKdW5pcXVlLmRheS5ldmVudHMgPC0gZXZlbnRzWywgLihldmVudCA9IHBhc3RlKGV2ZW50LCBjb2xsYXBzZSA9ICIgKyAiKSksIAogICAgICAgICAgICAgICAgICAgICAgICAgICBieSA9IC4oc3ViamVjdCwgZGF5KV0KdW5pcXVlLmRheS5ldmVudHNbLCBkYXkgOj0gYXMuY2hhcmFjdGVyKGRheSldCmRhdmlkLnNhbXBsZXMgPC0gbWVyZ2UoZGF2aWQuc2FtcGxlcywgdW5pcXVlLmRheS5ldmVudHMsIAogICAgICAgICAgICAgICAgICAgICAgIGJ5ID0gYygic3ViamVjdCIsICJkYXkiKSkKZGF2aWQuZGl2IDwtIG1lcmdlKGRhdmlkLmRpdiwgdW5pcXVlLmRheS5ldmVudHMsIGJ5LnggPSBjKCJzdWJqZWN0LmkiLCAiZGF5LmkiKSwKICAgICAgICAgICAgICAgICAgIGJ5LnkgPSBjKCJzdWJqZWN0IiwgImRheSIpKQpkYXZpZC5kaXYgPC0gbWVyZ2UoZGF2aWQuZGl2LCB1bmlxdWUuZGF5LmV2ZW50cywgYnkueCA9IGMoInN1YmplY3QuaiIsICJkYXkuaiIpLAogICAgICAgICAgICAgICAgICAgYnkueSA9IGMoInN1YmplY3QiLCAiZGF5IiksIHN1ZmZpeGVzID0gYygiLmkiLCAiLmoiKSkKYGBgCgpUaGUgbWFnbml0dWRlcyBvZiBkYXktdG8tZGF5IGNoYW5nZXMgaW4gY29tcG9zaXRpb24gZG9uJ3QgcmVmbGVjdCBzaWduaWZpY2FudCBldmVudHMuCmBgYHtyIGRhdmlkLXN0ZXBzaXplcy1kYXl9CnNldGtleShkYXZpZC5kaXYsIHN1YmplY3QuaSwgc3ViamVjdC5qKQpldmVudC5saW1zIDwtIGV2ZW50c1ssIC4oc3RhcnQgPSBtaW4oZGF5KSwgZW5kID0gbWF4KGRheSkpLCAKICAgICAgICAgICAgICAgICAgICAgYnkgPSAuKGV2ZW50LCBzdWJqZWN0KV0KZXZlbnQubGltcyA8LSBldmVudC5saW1zWyFncmVwbCgicHJlIiwgZXZlbnQpICYgIWdyZXBsKCJwb3N0IiwgZXZlbnQpXQpldmVudC5saW1zWywgZXZlbnQgOj0gZmFjdG9yKGxldmVscyA9IGMoInRyYXZlbCIsICJkaWFycmhlYSAxIiwgImRpYXJyaGVhIDIiLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIlNhbG1vbmVsbGEiKSwgZXZlbnQpXQpkYXZpZC5kaXZbc3ViamVjdC5pID09IHN1YmplY3QuaiAmIGRheS5kZWx0YSA9PSAxXSAlPiUgCiAgbXV0YXRlKGRheS5pID0gYXMubnVtZXJpYyhkYXkuaSkpICU+JSAKICBzZXRuYW1lcygic3ViamVjdC5pIiwgInN1YmplY3QiKSAlPiUgCiAgZ2dwbG90KGFlcyh4ID0gZGF5LmksIHkgPSBkaXN0YW5jZSkpICsKICBnZW9tX3JlY3QoZGF0YSA9IGV2ZW50LmxpbXMsIAogICAgbWFwcGluZyA9IGFlcyhmaWxsID0gZXZlbnQsIHhtaW4gPSBzdGFydCwgeG1heCA9IGVuZCwgCiAgICAgICAgICAgICAgICAgIHltaW4gPSAwLjEsIHltYXggPSAxLjA1CiAgICAgICAgICAgICAgICAgICksIGluaGVyaXQuYWVzID0gRkFMU0UsIGFscGhhID0gMC41KSArCiAgZ2VvbV9wb2ludCgpICsKICBmYWNldF93cmFwKH4gc3ViamVjdCwgbnJvdyA9IDIpCmBgYAoKRGlzdHJpYnV0aW9ucyBvZiBhbGwgZGlzdGFuY2VzIGZvciBhbGwgdGltZSBzY2FsZXMuCldlIHNlZSB0aGF0IGJvdGggbGVuZ3RoIGRpc3RyaWJ1dGlvbnMgYXJlIG11bHRpbW9kYWwsIGluZGljYXRpbmcgYXQgbGVhc3QgMiBjb21wb3NpdGlvbmFsICJsZW5ndGggc2NhbGVzLiIKV2UgYWxzbyBzZWUgdGhhdCB0aGUgdmFzdCBtYWpvcml0eSBvZiBBIGRpc3RhbmNlcyBiZWxvbmcgdG8gdGhlIGxvd2VzdCBtb2RlLCB3aGlsZSB0aGUgc2Vjb25kIGxvd2VzdCBtb2RlIG9mIEIgaXMgYXMgaGlnaCBhcyB0aGUgbG93ZXN0LCBpbmRpY2F0aW5nIHRoYXQgc3ViamVjdCBCIHNwZW5kcyBhIHNpZ25pZmljYW50IGFtb3VudCBvZiB0aW1lIChyZWxhdGl2ZSB0byB0aGUgbGVuZ3RoIG9mIHRoZSBlbnRpcmUgbWVhc3VyZW1lbnQpLgpgYGB7ciBkYXZpZC1hbGwtZGlzdC1kaXN0cmliLGZpZy53aWR0aD01LGZpZy5oZWlnaHQ9NX0KcDAgPC0gZ2dwbG90KGRhdmlkLmRpdltzdWJqZWN0LmkgPT0gc3ViamVjdC5qXSwgYWVzKHggPSBkaXN0YW5jZSkpIAphciA8LSAzIC8gNQpjZGYgPC0gcDAgKyBzdGF0X2VjZGYoYWVzKGNvbG9yID0gc3ViamVjdC5pKSkgKyBsYWJzKHkgPSAiRUNERiIpICsKICB0aGVtZShhc3BlY3QucmF0aW8gPSBhcikKZGVucyA8LSBwMCArIHN0YXRfZGVuc2l0eShhZXMoZmlsbCA9IHN1YmplY3QuaSksIGFscGhhID0gMC41LCAKICAgICAgICAgICAgICAgICAgICAgICAgICBwb3NpdGlvbiA9ICJpZGVudGl0eSIpICsKICB0aGVtZShhc3BlY3QucmF0aW8gPSBhcikKcGxvdF9ncmlkKGNkZiwgZGVucywgbnJvdyA9IDIsIGFsaWduID0gInYiKQpgYGAKCiMjIyBQYXRocwpgYGB7ciBkYXZpZC1wYXRoLXBsb3RzLGZpZy53aWR0aD03LGZpZy5oZWlnaHQ9N30KZGF2aWQuc3ViamVjdHMgPC0gYygiQSIsICJCIikKbmFtZXMoZGF2aWQuc3ViamVjdHMpIDwtIGRhdmlkLnN1YmplY3RzCnNldGtleShkYXZpZC5kaXYsIHN1YmplY3QuaSwgc3ViamVjdC5qKQpkbSA8LSBNYWtlRGlzdE1hdHJpeChkYXZpZC5kaXYsICJzYW1wbGUuaSIsICJzYW1wbGUuaiIpCmZpdCA8LSBDb29yZENNRFMoZG0pCnhmb3JtIDwtIGZpdCRwb2ludHMKc2V0Y29sb3JkZXIoeGZvcm0sIGMoInNhbXBsZSIsICJ4IiwgInkiKSkKc2V0a2V5KHhmb3JtLCBzYW1wbGUpCiMgcHV0IHNhbXBsZSBsYWJlbHMgYXQgZmlyc3QgMiBjb2x1bW5zCnNldGNvbG9yZGVyKGRhdmlkLmRpdiwgYygic2FtcGxlLmkiLCAic2FtcGxlLmoiLAogICAgICAgICAgICAgICAgICAgICAgICAgbmFtZXMoZGF2aWQuZGl2KVshKG5hbWVzKGRhdmlkLmRpdikgJWluJQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgYygic2FtcGxlLmkiLCAic2FtcGxlLmoiKSldKQogICAgICAgICAgICApCmRhdmlkLnNhbXBsZXNbLCBkYXkgOj0gYXMubnVtZXJpYyhkYXkpXQpzZXRjb2xvcmRlcihkYXZpZC5zYW1wbGVzLCBjKCJzYW1wbGUiLCAic3ViamVjdCIsICJkYXkiLCAiZXZlbnQiLCAiaWR4IiwgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgInN1YmouaWR4IikpCmdyYWYgPC0gZ3JhcGhfZnJvbV9kYXRhX2ZyYW1lKAogIGRhdmlkLmRpdltzdWJqZWN0LmkgPT0gc3ViamVjdC5qICYgaW5jcmVtZW50ID09IDFdLAogIGRpcmVjdGVkID0gVFJVRSwKICB2ZXJ0aWNlcyA9IGRhdmlkLnNhbXBsZXMKICApCnNldGtleSh4Zm9ybSwgc2FtcGxlKQp4Zm9ybSA8LSB4Zm9ybVtWKGdyYWYpJG5hbWVdCmxvIDwtIGNyZWF0ZV9sYXlvdXQoZ3JhZiwgIm1hbnVhbCIsIG5vZGUucG9zaXRpb25zID0geGZvcm0pCm5zaXplIDwtIDEKcDEgPC0gZ2dyYXBoKGxvKSArCiAgZ2VvbV9lZGdlX2xpbmsoYXJyb3cgPSBhcnJvdyhsZW5ndGggPSB1bml0KDMsICJwb2ludHMiKSwgdHlwZSA9ICJjbG9zZWQiKSwKICAgICAgICAgICAgICAgICBlbmRfY2FwID0gc3F1YXJlKGxlbmd0aCA9IDMsIHVuaXQgPSAicG9pbnRzIiksCiAgICAgICAgICAgICAgICAgZWRnZV93aWR0aCA9IDAuMikgKwogIGdlb21fbm9kZV9wb2ludChhZXMoY29sb3IgPSBkYXkpLCBzaXplID0gbnNpemUpICsKICBzY2FsZV9jb2xvcl9kaXN0aWxsZXIocGFsZXR0ZSA9ICJCbHVlcyIpICsKICBmYWNldF9ub2Rlcyh+IHN1YmplY3QpICsKICB0aGVtZV9ncmFwaChiYXNlX2ZhbWlseSA9ICJIZWx2ZXRpY2EiKSArCiAgdGhlbWUoYXNwZWN0LnJhdGlvID0gMSkKcDIgPC0gZ2dyYXBoKGxvKSArCiAgZ2VvbV9lZGdlX2xpbmsoYXJyb3cgPSBhcnJvdyhsZW5ndGggPSB1bml0KDMsICJwb2ludHMiKSwgdHlwZSA9ICJjbG9zZWQiKSwKICAgICAgICAgICAgICAgICBlbmRfY2FwID0gc3F1YXJlKGxlbmd0aCA9IDMsIHVuaXQgPSAicG9pbnRzIiksCiAgICAgICAgICAgICAgICAgZWRnZV93aWR0aCA9IDAuMikgKwogIGdlb21fbm9kZV9wb2ludChhZXMoY29sb3IgPSBldmVudCksIHNpemUgPSBuc2l6ZSkgKwogIGZhY2V0X25vZGVzKH4gc3ViamVjdCkgKwogIHRoZW1lX2dyYXBoKGJhc2VfZmFtaWx5ID0gIkhlbHZldGljYSIpICsKICB0aGVtZShhc3BlY3QucmF0aW8gPSAxKQpwbG90X2dyaWQocDEsIHAyLCBucm93ID0gMiwgYWxpZ24gPSAidiIpCmBgYApMYXlpbmcgYm90aCBzdWJqZWN0cyBhbG9uZyB0aGUgc2FtZSBheGVzIHdlIHNlZSBlYWNoIHN1YmplY3QgaXMgbW9yZSBzaW1pbGFyIHRvIHRoZW1zZWx2ZXMgdGhhbiB0aGV5IGFyZSB0byB0aGUgb3RoZXIgc3ViamVjdCwgZm9yIHRoZSBtb3N0IHBhcnQuClRoZSB1cHBlciByaWdodCByZXByZXNlbnRzIHN0YXRlcyBpbiB3aGljaCB0aGUgdHdvIHN1YmplY3RzIHJlc2VtYmxlZCBlYWNoIG90aGVyLgpJbnRlcmVzdGluZ2x5IG5vdCBhbGwgdGhlc2UgcG9pbnRzIHNlZW0gdG8gYmUgY2xvc2UgaW4gdGltZS4KU3ViamVjdCBCIG1ha2VzIGEgYnJpZWYgZXhjdXJzaW9uIHRvIGEgU3ViamVjdCBBLWxpa2Ugc3RhdGUgcG9zdCBTYWxtb25lbGxhLgoKRWlnZW52YWx1ZXMgYnkgcmFuazoKYGBge3IgZGF2aWQtZWlnZW4tcmFua30KZ2dwbG90KGZpdCRlaWdyYW5rLCBhZXMoeCA9IHJhbmssIHkgPSB2YWx1ZSBeIDIpKSArCiAgZ2VvbV9wb2ludCgpCmBgYAoKCgojIyMgVHJlZXMKCiMjIyMgVG9nZXRoZXIKCkhpZXJhcmNoaWNhbCBjbHVzdGVyaW5nIHJldmVhbHMgMyBtYWpvciBicmFuY2hlczogY2hhcmFjdGVyaXN0aWMgb2YgU3ViamVjdCBBLCBjaGFyYWN0ZXJpc3RpYyBvZiBTdWJqZWN0IEIsIGFuZCBTaGFyZWQgT3V0bGllciBTdGF0ZS4gCmBgYHtyIGRhdmlkLW1lcmdlZC10cmVlLGZpZy53aWR0aD03LGZpZy5oZWlnaHQ9MjB9CmRtIDwtIGRjYXN0KGRhdmlkLmRpdiwgc2FtcGxlLmkgfiBzYW1wbGUuaiwgdmFsdWUudmFyID0gImRpc3RhbmNlIikKcm4gPC0gZG0kc2FtcGxlLmkKZG0gPC0gZG1bLCAtMV0KZG0gPC0gYXMubWF0cml4KGRtKQpyb3duYW1lcyhkbSkgPC0gcm4KZGVuZHJvIDwtIGFzLmRlbmRyb2dyYW0oaGNsdXN0KGRpc3QoZG0pKSkKdW5pcXVlLmRheS5ldmVudHNbLCBkYXkgOj0gYXMuY2hhcmFjdGVyKGRheSldCnNldGtleSh1bmlxdWUuZGF5LmV2ZW50cywgc3ViamVjdCwgZGF5KQpkYXZpZC5zYW1wbGVzWywgZGF5IDo9IGFzLmNoYXJhY3RlcihkYXkpXQpkYXZpZC5zYW1wbGVzWywgc3RhdGUgOj0gewogIHN1YmogPC0gc3ViamVjdAogIGRkIDwtIGRheQogIHVuaXF1ZS5kYXkuZXZlbnRzWy4oc3ViaiwgZGQpLCBldmVudF0KfSwgYnkgPSAuKHN1YmplY3QsIGRheSldCnNldGtleShkYXZpZC5zYW1wbGVzLCBzYW1wbGUpCmRlbmRybyA8LSBkZW5kcmFwcGx5KGRlbmRybywgZnVuY3Rpb24oZCkgewogIGlmIChpcy5sZWFmKGQpKSB7CiAgICBzYW1wIDwtIGF0dHIoZCwgImxhYmVsIikKICAgIHN1YmogPC0gZGF2aWQuc2FtcGxlc1tzYW1wLCBzdWJqZWN0XQogICAgc3RhdGUgPC0gZGF2aWQuc2FtcGxlc1tzYW1wLCBzdGF0ZV0KICAgIGF0dHIoZCwgIm5vZGVQYXIiKSA8LSBhcHBlbmQoYXR0cihkLCAibm9kZVBhciIpLCBsaXN0KHN1YmplY3QgPSBzdWJqLCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHN0YXRlID0gc3RhdGUpKQogIH0KICBkCn0pCmdncmFwaChkZW5kcm8sICJkZW5kcm9ncmFtIikgKwogIGdlb21fZWRnZV9lbGJvdygpICsKICBnZW9tX25vZGVfcG9pbnQoYWVzKGZpbHRlciA9IGxlYWYsIHNoYXBlID0gc3ViamVjdCwgY29sb3IgPSBzdGF0ZSksIHNpemUgPSAxKSArCiAgdGhlbWVfZ3JhcGgoYmFzZV9mYW1pbHkgPSAiSGVsdmV0aWNhIikgKwogICMgdGhlbWUoYXNwZWN0LnJhdGlvID0gMSkgKyAKICBjb29yZF9mbGlwKCkKYGBgCgojIyMjIFNlcGFyYXRlCkNsdXN0ZXJpbmcgc2VwYXJhdGVseSBzaG93cyB0aGF0IFN1YmplY3QgQiBoYXMgZGlzdGluY3QgcHJlLSBhbmQgcG9zdC1TYWxtb25lbGxhIHN0YXRlcywgYnV0IHRoZSB2YXJpb3VzIGV2ZW50cyBpbiBTdWJqZWN0IEEncyBsaWZlIGRpZG4ndCBjcmVhdGUgYWx0ZXJuYXRlIHN0YWJsZSBzdGF0ZXMgdGhhdCB3ZXJlIHNpZ25pZmljYW50bHkgZGlmZmVyZW50LgoKYGBge3IgZGF2aWQtZXZlbnQtdHJlZXMsZmlnLmhlaWdodD05LGZpZy53aWR0aD03fQpzZXRrZXkoZGF2aWQuZGl2LCBzdWJqZWN0LmksIHN1YmplY3QuaikKZGVuZHJvcyA8LSBsYXBwbHkoZGF2aWQuc3ViamVjdHMsIGZ1bmN0aW9uKHN1YmopIHsKICBzZCA8LSBkYXZpZC5kaXZbLihzdWJqLCBzdWJqKV0KICBkbSA8LSBkY2FzdChzZCwgc2FtcGxlLmkgfiBzYW1wbGUuaiwgdmFsdWUudmFyID0gImRpc3RhbmNlIikKICBybiA8LSBkbSRzYW1wbGUuaQogIGRtIDwtIGRtWywgLTFdCiAgZG0gPC0gYXMubWF0cml4KGRtKQogIHJvd25hbWVzKGRtKSA8LSBybgogIGhjIDwtIGhjbHVzdChkaXN0KGRtKSkKICBkZW5kcm8gPC0gYXMuZGVuZHJvZ3JhbShoYykKICByZXR1cm4oZGVuZHJvKQp9CikKdW5pcXVlLmRheS5ldmVudHNbLCBkYXkgOj0gYXMuY2hhcmFjdGVyKGRheSldCiMgc2V0a2V5KGV2ZW50cywgc3ViamVjdCkKc2V0a2V5KHVuaXF1ZS5kYXkuZXZlbnRzLCBzdWJqZWN0LCBkYXkpCnNldGtleShkYXZpZC5zYW1wbGVzLCBzYW1wbGUpCmRlbmRyb3MgPC0gbGFwcGx5KGRhdmlkLnN1YmplY3RzLCBmdW5jdGlvbihzdWJqKSB7CiAgZGVuZHJvIDwtIGRlbmRyb3NbW3N1YmpdXQogIGRlbmRybyA8LSBkZW5kcmFwcGx5KGRlbmRybywgZnVuY3Rpb24oZCkgewogICAgaWYgKGlzLmxlYWYoZCkpIHsKICAgICAgZGRheSA8LSBkYXZpZC5zYW1wbGVzW2F0dHIoZCwgImxhYmVsIiksIGFzLmNoYXJhY3RlcihkYXkpXQogICAgICBldiA8LSB1bmlxdWUuZGF5LmV2ZW50c1suKHN1YmosIGRkYXkpLCBldmVudF0KICAgICAgYXR0cihkLCAibm9kZVBhciIpIDwtIGFwcGVuZChhdHRyKGQsICJub2RlUGFyIiksIGxpc3QoCiAgICAgICAgZGF5ID0gYXMubnVtZXJpYyhkZGF5KSwKICAgICAgICBldmVudCA9IGV2KSkKICAgIH0KICAgIGQKICB9KQogICMgcHJvcGFnYXRlIG1ldGFkYXRhIGJhY2sgdXAgdGhlIHRyZWUKICBkZW5kcm8gPC0gdHJlZV9hcHBseShkZW5kcm8sIGZ1bmN0aW9uKG5vZGUsIGNoaWxkcmVuLCBkZXB0aCwgdHJlZSkgewogIGlmICghaXMubGVhZihub2RlKSkgewogICAgZXZlbnRzIDwtIHNhcHBseShjaGlsZHJlbiwgZnVuY3Rpb24oYykgewogICAgICBhdHRyKGMsICJub2RlUGFyIikkZXZlbnQKICAgIH0pCiAgICBldmVudHMgPC0gdW5pcXVlKGV2ZW50cykKICAgIGlmIChsZW5ndGgoZXZlbnRzKSA9PSAxICYgIWFueU5BKGV2ZW50cykpIHsKICAgICAgYXR0cihub2RlLCAibm9kZVBhciIpIDwtIGFwcGVuZChhdHRyKG5vZGUsICJub2RlUGFyIiksIGxpc3QoZXZlbnQgPSBldmVudHMpKQogICAgfSBlbHNlIHsKICAgICAgYXR0cihub2RlLCAibm9kZVBhciIpIDwtIGFwcGVuZChhdHRyKG5vZGUsICJub2RlUGFyIiksIGxpc3QoZXZlbnQgPSBOQSkpCiAgICB9CiAgfQogIG5vZGUKICB9LCBkaXJlY3Rpb24gPSAidXAiKQogIGRlbmRybwp9KQpkZW5kcm8ucGxvdHMgPC0gbGFwcGx5KGRlbmRyb3MsIGZ1bmN0aW9uKGRlbmQpIHsKICBnZ3JhcGgoZGVuZCwgImRlbmRyb2dyYW0iLCBjaXJjdWxhciA9IFRSVUUpICsKICAgIGdlb21fZWRnZV9lbGJvdyhhZXMoY29sb3IgPSBub2RlMi5ldmVudCkpICsKICAgIGdlb21fbm9kZV9wb2ludChhZXMoZmlsdGVyID0gbGVhZiwgY29sb3IgPSBkYXkpLCBzaXplID0gMC42KSArCiAgICBzY2FsZV9jb2xvcl9kaXN0aWxsZXIocGFsZXR0ZSA9ICJTcGVjdHJhbCIpICsKICAgIHRoZW1lX2dyYXBoKGJhc2VfZmFtaWx5ID0gIkhlbHZldGljYSIpICsKICAgIHRoZW1lKGFzcGVjdC5yYXRpbyA9IDEpCn0pCnBsb3RfZ3JpZChwbG90bGlzdCA9IGRlbmRyby5wbG90cywgbnJvdyA9IDIsIGxhYmVscyA9ICJBVVRPIikKYGBgCgpTdWJqZWN0IEEgZG9lc24ndCBzZWVtIHRvIGhhdmUgYSBkaXN0aW5jdCAidHJhdmVsaW5nIiBjb21wb3NpdGlvbi4KSW5kZWVkIGl0IHNlZW1zIHRoZSBkaXN0YW5jZSBiZXR3ZWVuIHRyYXZlbGluZyBhbmQgVVMgY29tcG9zaXRpb25zIGRvZXNuJ3Qgc2VlbSBub3RpY2VhYmx5IGxhcmdlciB0aGFuIHRoZSBkaXN0YW5jZSBiZXR3ZWVuIFVTIGNvbXBvc2l0aW9ucy4KTWVhbmluZyB0cmF2ZWxpbmcgZGlkIG5vdCBkZXN0YWJpbGl6ZSB0aGUgbWljcm9iaW9tZSBhbnkgbW9yZSB0aGFuIGJhc2VsaW5lIGZsdWN0dWF0aW9ucyB3aGlsZSBsaXZpbmcgaW4gdGhlIFVTLgpQZXJoYXBzIHRoaXMgaXMgZHVlIHRvIG1hbnkgT1RVcyByZW1haW5pbmcgc3RhYmxlIHRocm91Z2ggdGhlIGR1cmF0aW9uIG9mIHRyYXZlbC4KClN1YmplY3QgQiBzaG93cyBjbGVhciBwcmUtIGFuZCBwb3N0LVNhbG1vbmVsbGEgc3RhdGVzLCBhcyByZXBvcnRlZCBpbiB0aGUgb3JpZ2luYWwgbWFudXNjcmlwdC4KUGVyaGFwcyB0aGUgcG9zdC1TYWxtb25lbGxhIHN0YXRlIGlzIHNlcGFyYXRlIGJlY2F1c2Ugb2YgdGhlIGV4dGluY3Rpb24gb2YgY2x1c3RlciA0IChzZWUgb3JpZ2luYWwgcGFwZXIpIGR1cmluZyBpbmZlY3Rpb24sIHJlbmRlcmluZyByZXR1cm4gdG8gdGhlIHByZS1TYWxtb25lbGxhIHN0YXRlIGltcG9zc2libGU/CgojIyBHb3Jkb24gZXQgYWwgKGNob2xlcmEpCmBgYHtyfQpnb3Jkb24gPC0gZnJlYWQocGFzdGUwKGRhdGEuZGlyLCAiY2hvbGVyYS9nb3Jkb24ub3R1cyIpLAogICAgICAgICAgICAgICAgY29sLm5hbWVzID0gYygic2FtcGxlIiwgIm90dSIsICJjb3VudCIpKQojIGV4dHJhY3Qgc2FtcGxlIGluZm8KZ29yZG9uLnNhbXBsZXMgPC0gdW5pcXVlKGdvcmRvblssIC4oc2FtcGxlKV0pCiMgY3JlYXRlIGEgZHVtbXkgJ3NhbXBsZSBpbmRleCcgdG8gaGVscCByZW1vdmUgcmVjaXByb2NhbCBzYW1wbGUgcGFpcnMgbGF0ZXIgCmdvcmRvbi5zYW1wbGVzWywgaWR4IDo9IDE6Lk5dCmdvcmRvbi5zYW1wbGVzWywgYygic3ViamVjdCIsICJzdGF0ZSIsICJpZCIpIDo9IHRzdHJzcGxpdChzYW1wbGUsICJfIildCmdvcmRvbi5zYW1wbGVzW2dyZXAoImQiLCBpZCkgJiBzdGF0ZSA9PSAicmVjb3ZlcnkiLCB0aW1lLnVuaXQgOj0gImRheSJdCmdvcmRvbi5zYW1wbGVzWyFncmVwKCJkIiwgaWQpLCB0aW1lLnVuaXQgOj0gImhvdXIiXQpnb3Jkb24uc2FtcGxlc1tpZCA9PSAiZW5kIiwgdGltZS51bml0IDo9ICJob3VyIl0Kc2V0a2V5KGdvcmRvbi5zYW1wbGVzLCB0aW1lLnVuaXQpCmdvcmRvbi5zYW1wbGVzWyJob3VyIiwgaG91ciA6PSBhcy5udW1lcmljKGlkKV0KZ29yZG9uLnNhbXBsZXNbImRheSIsIGhvdXIgOj0gMjQgKiBhcy5udW1lcmljKHN1YigiZCIsICIiLCBpZCkpXQpzdWJqZWN0cyA8LSB1bmlxdWUoZ29yZG9uLnNhbXBsZXMkc3ViamVjdCkKIyBzZXQgZW5kIGhvdXIgdG8gbGFzdCBob3VyICsgMSwgZGF5cyB0byBlbmQgaG91ciArIDI0ICogZGF5cwpnb3Jkb24uc2FtcGxlc1ssIGhvdXIgOj0gewogIG1heGhyIDwtIG1heCguU0RbImhvdXIiXVtpZCAhPSAiZW5kIl0kaG91cikKICBlbmRociA8LSBtYXhociArIDEKICBob3VyW2lkID09ICJlbmQiXSA8LSBlbmRocgogIGhvdXJbdGltZS51bml0ID09ICJkYXkiXSA8LSBob3VyW3RpbWUudW5pdCA9PSAiZGF5Il0gKyBlbmRocgogIGhvdXIKfSwgYnkgPSBzdWJqZWN0XQojIGFsbCBzYW1wbGVzIHZzIGFsbCBzYW1wbGVzCmdvcmRvbi5kaXYgPC0gZGF0YS50YWJsZShleHBhbmQuZ3JpZChzYW1wbGUuaSA9IGdvcmRvbi5zYW1wbGVzJHNhbXBsZSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHNhbXBsZS5qID0gZ29yZG9uLnNhbXBsZXMkc2FtcGxlKQogICAgICAgICAgICAgICAgICAgICAgICAgKQojIG1lcmdlIHNhbXBsZSBpbmZvCmdvcmRvbi5kaXYgPC0gbWVyZ2UoZ29yZG9uLmRpdiwgZ29yZG9uLnNhbXBsZXMsIGJ5LnggPSAic2FtcGxlLmkiLCAKICAgICAgICAgICAgICAgICAgICBieS55ID0gInNhbXBsZSIKICAgICAgICAgICAgICAgICAgICApCmdvcmRvbi5kaXYgPC0gbWVyZ2UoZ29yZG9uLmRpdiwgZ29yZG9uLnNhbXBsZXMsIGJ5LnggPSAic2FtcGxlLmoiLCAKICAgICAgICAgICAgICAgICAgICBieS55ID0gInNhbXBsZSIsIHN1ZmZpeGVzID0gYygiLmkiLCAiLmoiKQogICAgICAgICAgICAgICAgICAgICkKIyByZW1vdmUgaW52ZXJzZSBwYWlyaW5ncwpnb3Jkb24uZGl2IDwtIGdvcmRvbi5kaXZbaWR4LmogPj0gaWR4LmldCiMgcmVtb3ZlIGR1bW15IHZhcmlhYmxlCmdvcmRvbi5kaXZbLCAiOj0iIChpZHguaSA9IE5VTEwsIGlkeC5qID0gTlVMTCldCmdvcmRvblssIGxvZy5jb3VudCA6PSBsb2coY291bnQpXQpnb3Jkb24Kc2V0a2V5KGdvcmRvbiwgc2FtcGxlKQpnb3Jkb24uZGl2WywganNkIDo9IHsKICBpZiAoc2FtcGxlLmkgPT0gc2FtcGxlLmopIHsKICAgIDAKICB9IGVsc2V7CiAgICBzaSA8LSBzYW1wbGUuaQogICAgc2ogPC0gc2FtcGxlLmoKICAgIHNkIDwtIGdvcmRvbltjKHNpLCBzaildCiAgICBtIDwtIGRjYXN0KHNkLCBvdHUgfiBzYW1wbGUsIHZhbHVlLnZhciA9ICJjb3VudCIpCiAgICBtIDwtIGFzLm1hdHJpeChtWywgMjozXSkKICAgIG1baXMubmEobSldIDwtIDAKICAgIGdlbkpTRChtKQogIH0KfSwgYnkgPSAuKHNhbXBsZS5pLCBzYW1wbGUuaildCmludiA8LSBnb3Jkb24uZGl2W3NhbXBsZS5pICE9IHNhbXBsZS5qXQpzZXRuYW1lcyhpbnYsIG5hbWVzKGludiksIHNhcHBseShuYW1lcyhpbnYpLCBmdW5jdGlvbih4KSB7CiAgaWYgKGdyZXBsKCJcXC5pIiwgeCkpIHsKICAgIGdzdWIoIlxcLmkiLCAiXFwuaiIsIHgpCiAgfSBlbHNlIGlmIChncmVwbCgiXFwuaiIsIHgpKSB7CiAgICBnc3ViKCJcXC5qIiwgIlxcLmkiLCB4KQogIH0gZWxzZSB7CiAgICB4CiAgfQp9KSkKZ29yZG9uLmRpdiA8LSByYmluZChnb3Jkb24uZGl2LCBpbnYpCmdvcmRvbi5kaXZbLCBkaXN0YW5jZSA6PSBzcXJ0KGpzZCldCmBgYAoKRGF2aWQtc3R5bGUgZGl2ZXJnZW5jZSBtYXRyaWNlcy4KRGFyayBvbi1kaWFnb25hbCBzcXVhcmVzIHJlcHJlc2VudCBvY2N1cGF0aW9uIG9mIHN0YWJsZSBzdGF0ZXMuCk1vc3QgcGF0aWVudHMgaGF2ZSBkaXN0aW5jdCBzdGFibGUgc3RhdGVzLgpgYGB7ciBnb3Jkb24tZGl2LW1hdHJpY2VzLGZpZy53aWR0aD03LGZpZy5oZWlnaHQ9N30Kc2V0a2V5KGdvcmRvbi5kaXYsIHN1YmplY3QuaSwgc3ViamVjdC5qKQpzdWJqZWN0cyA8LSBzb3J0KHN1YmplY3RzKQpuYW1lcyhzdWJqZWN0cykgPC0gc3ViamVjdHMKZ29yZG9uLmRpdlssICI6PSIgKGhvdXIuaSA9IGFzLmNoYXJhY3Rlcihob3VyLmkpLCBob3VyLmogPSBhcy5jaGFyYWN0ZXIoaG91ci5qKSldCnBsb3RzIDwtIGxhcHBseShzdWJqZWN0cywgZnVuY3Rpb24oc3ViaikgewogIHNkIDwtIGdvcmRvbi5kaXZbLihzdWJqLCBzdWJqKV0KICB0cyA8LSBhcy5udW1lcmljKHVuaXF1ZShzZCRob3VyLmkpKQogIGxpbXMgPC0gYXMuY2hhcmFjdGVyKHNvcnQodHMpKQogIHAgPC0gZ2dwbG90KHNkLCBhZXMoeCA9IGhvdXIuaSwgeSA9IGhvdXIuaikpICsKICAgIGdlb21fdGlsZShhZXMoZmlsbCA9IGpzZCkpICsKICAgIHNjYWxlX3hfZGlzY3JldGUobGltaXRzID0gbGltcykgKwogICAgc2NhbGVfeV9kaXNjcmV0ZShsaW1pdHMgPSBsaW1zKSArCiAgICB0aGVtZShhc3BlY3QucmF0aW8gPSAxLAogICAgICAgICAgYXhpcy50ZXh0ID0gZWxlbWVudF9ibGFuaygpLAogICAgICAgICAgYXhpcy50aWNrcyA9IGVsZW1lbnRfYmxhbmsoKSkKfSkKcGxvdF9ncmlkKHBsb3RsaXN0ID0gcGxvdHMsIG5jb2wgPSAyLCBsYWJlbHMgPSBuYW1lcyhwbG90cyksIGFsaWduID0gImh2IikKYGBgCgpUaW1lLWxhZyBkaXZlcmdlbmNlczoKYGBge3IgZ29yZG9uLWxhZy1qc2R9CmdvcmRvbi5kaXZbLCBkZWx0YS50IDo9IGFzLm51bWVyaWMoaG91ci5qKSAtIGFzLm51bWVyaWMoaG91ci5pKV0KcGxvdHMgPC0gbGFwcGx5KHN1YmplY3RzLCBmdW5jdGlvbihzdWJqKSB7CiAgc2QgPC0gZ29yZG9uLmRpdlsuKHN1YmosIHN1YmopXQogIHNkIDwtIHNkW2RlbHRhLnQgPiAwXQogIHAgPC0gZ2dwbG90KHNkLCBhZXMoeCA9IGRlbHRhLnQsIHkgPSBqc2QpKSArCiAgICBnZW9tX3BvaW50KHNpemUgPSAwLjEpICsKICAgIGdlb21fc21vb3RoKGNvbG9yID0gImJsdWUiKSArCiAgICBzY2FsZV94X2xvZzEwKCkgKwogICAgbGFicyh4ID0gImxhZyAoaG91cnMpIikKICBwCn0pCnBsb3RfZ3JpZChwbG90bGlzdCA9IHBsb3RzLCBhbGlnbiA9ICJodiIsIGxhYmVscyA9IG5hbWVzKHBsb3RzKSwKICAgICAgICAgIG5yb3cgPSAzKQpgYGAKCkRpc3RyaWJ1dGlvbnMgb2YgZGl2ZXJnZW5jZXMgc2hvdyB0aGF0IGZvciBhbGwgcGF0aWVudHMsIGRpYXJyaGVhIGFuZCByZWNvdmVyeSBzdGF0ZXMgYXJlIG1vcmUgc2ltaWxhciB0byB0aGVtc2VsdmVzIHRoYW4gdG8gZWFjaCBvdGhlciAoY3Jvc3Mtc3RhdGUgZGl2ZXJnZW5jZXMgYXJlIGxhcmdlKS4KSW4gbW9zdCBwYXRpZW50cyAoZXhjZXB0IEUpIHRoZSByZWNvdmVyeSBtaWNyb2Jpb21lIGlzIGFjdHVhbGx5IGxlc3Mgc3RhYmxlIHRoYW4gdGhlIGRpYXJyaGVhIG1pY3JvYmlvbWU6IHRoZSBkaWFycmhlYSBkaXZlcmdlbmNlcyB0ZW5kIHRvIGJlIHNtYWxsZXIuCioqSG93ZXZlcioqIHRoaXMgY291bGQgYWxzbyBiZSBkdWUgdG8gdGhlIGRlbnNlciB0ZW1wb3JhbCBzYW1wbGluZyBkdXJpbmcgdGhlIGRpYXJyaGVhIHBlcmlvZC4KV2Ugc2hvdWxkIHNjYWxlIHRoaXMgYnkgdGhlIHRpbWUgaW50ZXJ2YWwgc29tZWhvdywgc2luY2UgaXQgdmFyaWVzLgpgYGB7ciBnb3Jkb24tZGlzdC1kaXN0cmlifQpnb3Jkb24uZGl2Wywgc3RhdGUgOj0gewogIGlmIChzdGF0ZS5pID09IHN0YXRlLmopIHN0YXRlLmkKICBlbHNlICJjcm9zcyIKfSwgYnkgPSAuKHN0YXRlLmksIHN0YXRlLmopXSAgCnAwIDwtIGdvcmRvbi5kaXZbKHN1YmplY3QuaSA9PSBzdWJqZWN0LmopICYgKGRlbHRhLnQgPiAwKV0gJT4lIAogIGdncGxvdChhZXMoeCA9IGRpc3RhbmNlKSkKY2RmIDwtIHAwICsgc3RhdF9lY2RmKGFlcyhjb2xvciA9IHN0YXRlKSkgKyBmYWNldF93cmFwKH4gc3ViamVjdC5pLCBucm93ID0gMSkgKyAKICBsYWJzKHkgPSAiRUNERiIpICsKICB0aGVtZShheGlzLnRleHQueCA9IGVsZW1lbnRfdGV4dChhbmdsZSA9IDkwLCB2anVzdCA9IDAuNSwgaGp1c3QgPSAxKSkKZGVucyA8LSBwMCArIHN0YXRfZGVuc2l0eShhZXMoZmlsbCA9IHN0YXRlKSwgYWxwaGEgPSAwLjMsCiAgICAgICAgICAgICAgICAgICAgICAgICAgcG9zaXRpb24gPSAiaWRlbnRpdHkiKQpkZW5zIDwtIGRlbnMgKwogIGZhY2V0X3dyYXAofiBzdWJqZWN0LmksIG5yb3cgPSAxKSArCiAgdGhlbWUoYXhpcy50ZXh0LnggPSBlbGVtZW50X3RleHQoYW5nbGUgPSA5MCwgdmp1c3QgPSAwLjUsIGhqdXN0ID0gMSkpCnBsb3RfZ3JpZChjZGYsIGRlbnMsIG5yb3cgPSAyLCBhbGlnbiA9ICJ2IikKYGBgCgojIyMgUGF0aHMKTURTIG9mIGFsbCBzdWJqZWN0cyBzaW11bHRhbmVvdXNseSBzaG93cyB0aGF0IGRpYXJyaGVhL3JlY292ZXJ5IHNlcGFyYXRlcyB0aW1lIHBvaW50cyBtb3JlIHRoYW4gc3ViamVjdC4KYGBge3IgZ29yZG9uLXBhdGhzfQpzZXRrZXkoZ29yZG9uLmRpdiwgc3ViamVjdC5pLCBzdWJqZWN0LmopCnNldGtleShnb3Jkb24uc2FtcGxlcywgc3ViamVjdCkKZWRnZXMgPC0gbGFwcGx5KHN1YmplY3RzLCBmdW5jdGlvbihzdWJqKSB7CiAgc2QgPC0gZ29yZG9uLmRpdlsuKHN1YmosIHN1YmopXQogIHRzIDwtIGFzLm51bWVyaWModW5pcXVlKHNkJGhvdXIuaSkpCiAgdHMgPC0gYXMuY2hhcmFjdGVyKHNvcnQodHMpKQogIGVqIDwtIGRhdGEudGFibGUodGkgPSB0c1stbGVuZ3RoKHRzKV0sIHRqID0gdHNbLTFdKQogIHNhbXBzIDwtIGdvcmRvbi5zYW1wbGVzW3N1YmosIC4oc2FtcGxlLCBob3VyKV0KICBzYW1wc1ssIGhvdXIgOj0gYXMuY2hhcmFjdGVyKGhvdXIpXQogIGVqIDwtIG1lcmdlKGVqLCBzYW1wcywgYnkueCA9ICJ0aSIsIGJ5LnkgPSAiaG91ciIpCiAgZWogPC0gbWVyZ2UoZWosIHNhbXBzLCBieS54ID0gInRqIiwgYnkueSA9ICJob3VyIiwgc3VmZml4ZXMgPSBjKCIuaSIsICIuaiIpKQogIGVqWywgLihzYW1wbGUuaSwgc2FtcGxlLmopXQp9KSAlPiUgcmJpbmRsaXN0KCkKZ3JhZiA8LSBncmFwaF9mcm9tX2RhdGFfZnJhbWUoZWRnZXMsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGRpcmVjdGVkID0gVFJVRSwgdmVydGljZXMgPSBnb3Jkb24uc2FtcGxlcykKZG0gPC0gTWFrZURpc3RNYXRyaXgoZ29yZG9uLmRpdiwgInNhbXBsZS5pIiwgInNhbXBsZS5qIikKZml0IDwtIENvb3JkQ01EUyhkbSkKeGZvcm0gPC0gZml0JHBvaW50cwojIG9yZGVyCnNldGtleSh4Zm9ybSwgc2FtcGxlKQp4Zm9ybSA8LSB4Zm9ybVtWKGdyYWYpJG5hbWVdCmxvIDwtIGNyZWF0ZV9sYXlvdXQoZ3JhZiwgIm1hbnVhbCIsIG5vZGUucG9zaXRpb25zID0geGZvcm0pCmdncmFwaChsbykgKwogIGdlb21fZWRnZV9saW5rKGFycm93ID0gYXJyb3codHlwZSA9ICJjbG9zZWQiLCBsZW5ndGggPSB1bml0KDMsICJwb2ludHMiKSksCiAgICAgICAgICAgICAgICAgZWRnZV93aWR0aCA9IDAuMiwgZW5kX2NhcCA9IHNxdWFyZShsZW5ndGggPSAzLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgdW5pdCA9ICJwb2ludHMiKSkgKwogIGdlb21fbm9kZV9wb2ludChhZXMoY29sb3IgPSBzdGF0ZSkpICsKICAjIHNjYWxlX3NoYXBlX21hbnVhbCh2YWx1ZXMgPSBzZXEoMSwgbGVuZ3RoKHN1YmplY3RzKSkpICsKICBmYWNldF9ub2Rlcyh+IHN1YmplY3QsIG5yb3cgPSAyKSArCiAgdGhlbWVfZ3JhcGgoYmFzZV9mYW1pbHkgPSAiSGVsdmV0aWNhIikgKwogIHRoZW1lKGFzcGVjdC5yYXRpbyA9IDEpCmdncGxvdChmaXQkZWlncmFuaywgYWVzKHggPSByYW5rLCB5ID0gdmFsdWUgXiAyKSkgKwogIGdlb21fcG9pbnQoKSAKYGBgCgpBbGwgcG9pbnRzIHBsb3Qgc2hvdyByZWNvdmVyeSBhbmQgZGlhcnJoZWEgY2x1c3RlciBzZXBhcmF0ZWx5IGZvciBhbGwgcGF0aWVudHMsIHdpdGggZGlhcnJoZWEgaGF2aW5nIGdyZWF0ZXIgc3ByZWFkOgpgYGB7cn0KZ2dyYXBoKGxvKSArCiAgZ2VvbV9ub2RlX3BvaW50KGFlcyhjb2xvciA9IHN0YXRlLCBzaGFwZSA9IHN1YmplY3QpKSArCiAgc2NhbGVfc2hhcGVfbWFudWFsKHZhbHVlcyA9IHNlcSh1bmlxdWVOKGdvcmRvbi5zYW1wbGVzJHN1YmplY3QpKSkgKwogIHRoZW1lX2dyYXBoKGJhc2VfZmFtaWx5ID0gIkhlbHZldGljYSIpICsKICB0aGVtZShhc3BlY3QucmF0aW8gPSAxKQpgYGAKCiMjIyBUcmVlCgpBbGwgdG9nZXRoZXIuCkFnYWluIHNlcGFyYXRpb24gaXMgbW9zdGx5IGRpYXJyaGVhL3JlY292ZXJ5LgpIb3dldmVyLCBzb21lIGRpYXJyaGVhIHBvaW50cyBhcmUgY2xvc2VyIHRvIHJlY292ZXJ5IHBvaW50cyB0aGFuIHRoZXkgYXJlIHRvIHRoZSBtYWpvcml0eSBvZiBkaWFycmhlYSBwb2ludHMuClRoaXMgY2FuIGFsc28gYmUgc2VlbiBpbiB0aGUgbGFzdCBwbG90IHdoZXJlIHRoZSB0d28gJ2Nsb3VkcycgZW5tZXNoLgpgYGB7cixmaWcud2lkdGg9NyxmaWcuaGVpZ2h0PTd9CmRtIDwtIGRjYXN0KGdvcmRvbi5kaXYsIHNhbXBsZS5pIH4gc2FtcGxlLmosIHZhbHVlLnZhciA9ICJkaXN0YW5jZSIpCnJuIDwtIGRtWywgc2FtcGxlLmldIApkbSA8LSBhcy5tYXRyaXgoZG1bLCAtMV0pCnJvd25hbWVzKGRtKSA8LSBybgpkZW5kcm8gPC0gYXMuZGVuZHJvZ3JhbShoY2x1c3QoZGlzdChkbSkpKQojIGFubm90YXRlCnNldGtleShnb3Jkb24uc2FtcGxlcywgc2FtcGxlKQpkZW5kcm8gPC0gZGVuZHJhcHBseShkZW5kcm8sIGZ1bmN0aW9uKGQpIHsKICBpZiAoaXMubGVhZihkKSkgewogICAgc2FtcC5pZCA8LSBhdHRyKGQsICJsYWJlbCIpCiAgICBzYW1wbGUgPC0gZ29yZG9uLnNhbXBsZXNbc2FtcC5pZF0KICAgIHN1YmogPC0gc2FtcGxlJHN1YmplY3QKICAgIHN0YXRlIDwtIHNhbXBsZSRzdGF0ZQogICAgYXR0cihkLCAibm9kZVBhciIpIDwtIGFwcGVuZChhdHRyKGQsICJub2RlUGFyIiksIGxpc3Qoc3ViamVjdCA9IHN1YmosCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBzdGF0ZSA9IHN0YXRlKSkKICB9CiAgZAp9KQpsbyA8LSBjcmVhdGVfbGF5b3V0KGRlbmRybywgImRlbmRyb2dyYW0iLCBjaXJjdWxhciA9IFRSVUUpCmdncmFwaChsbykgKwogIGdlb21fZWRnZV9lbGJvdygpICsKICBnZW9tX25vZGVfcG9pbnQoYWVzKGZpbHRlciA9IGxlYWYsIHNoYXBlID0gc3ViamVjdCwgY29sb3IgPSBzdGF0ZSkpICsKICBzY2FsZV9zaGFwZV9tYW51YWwodmFsdWVzID0gc2VxKDEsIGxlbmd0aChzdWJqZWN0cykpKSArCiAgdGhlbWVfZ3JhcGgoYmFzZV9mYW1pbHkgPSAiSGVsdmV0aWNhIikgKwogIHRoZW1lKGFzcGVjdC5yYXRpbyA9IDEpCmBgYAoKYGBge3IgZ29yZG9uLXN0YXRlLWNsdXN0ZXJzLGZpZy53aWR0aD03LGZpZy5oZWlnaHQ9MTB9CnNldGtleShnb3Jkb24uZGl2LCBzdWJqZWN0LmksIHN1YmplY3QuaikKZ29yZG9uLnNhbXBsZXNbLCBob3VyIDo9IGFzLmNoYXJhY3Rlcihob3VyKV0Kc2V0a2V5KGdvcmRvbi5zYW1wbGVzLCBzdWJqZWN0LCBob3VyKQp0cmVlcyA8LSBsYXBwbHkoc3ViamVjdHMsIGZ1bmN0aW9uKHN1YmopIHsKICBzZCA8LSBnb3Jkb24uZGl2Wy4oc3Viaiwgc3ViaildCiAgc2QgPC0gZGNhc3Qoc2QsIGhvdXIuaSB+IGhvdXIuaiwgdmFsdWUudmFyID0gImRpc3RhbmNlIikKICBybiA8LSBzZFssIGhvdXIuaV0KICBkbSA8LSBhcy5tYXRyaXgoc2RbLCAtMV0pCiAgcm93bmFtZXMoZG0pIDwtIHJuCiAgZGVuZHJvIDwtIGFzLmRlbmRyb2dyYW0oaGNsdXN0KGRpc3QoZG0pKSkKICAjIG1lcmdlIHRpbWUgZGF0YSBhbmQgc3RhdGUKICBzZFssIHRpbWUuaW5kZXggOj0gZnJhbmsoYXMubnVtZXJpYyhob3VyLmkpKV0KICBzZXRrZXkoc2QsIGhvdXIuaSkKICBkZW5kcm8gPC0gZGVuZHJhcHBseShkZW5kcm8sIGZ1bmN0aW9uKG5vZGUpIHsKICAgIGlmIChpcy5sZWFmKG5vZGUpKSB7CiAgICAgIGxhYmwgPC0gYXR0cihub2RlLCAibGFiZWwiKQogICAgICB0IDwtIGFzLm51bWVyaWMobGFibCkKICAgICAgdGltZS5pbmRleCA8LSBhcy5udW1lcmljKHNkW2xhYmwsIHRpbWUuaW5kZXhdKQogICAgICBzdGF0ZSA8LSBnb3Jkb24uc2FtcGxlc1suKHN1YmosIGxhYmwpLCBzdGF0ZV0KICAgICAgYXR0cihub2RlLCAibm9kZVBhciIpIDwtIGFwcGVuZChhdHRyKG5vZGUsICJub2RlUGFyIiksIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGxpc3QoaG91ciA9IHQsIHRpbWUuaW5kZXggPSB0aW1lLmluZGV4LAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgc3RhdGUgPSBzdGF0ZSkKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICApCiAgICB9CiAgICBub2RlCiAgfSkKICAjIHByb3BhZ2F0ZSBzdGF0ZSB1cHdhcmRzIHRocm91Z2ggYnJhbmNoIG5vZGVzCiAgZGVuZHJvIDwtIHRyZWVfYXBwbHkoZGVuZHJvLCBmdW5jdGlvbihub2RlLCB0cmVlLCBkZXB0aCwgY2hpbGRyZW4pIHsKICAgIGlmICghaXMubGVhZihub2RlKSkgewogICAgICBjaGlsZC5zdGF0ZXMgPC0gc2FwcGx5KGNoaWxkcmVuLCBmdW5jdGlvbihuKSB7CiAgICAgICAgYXR0cihuLCAibm9kZVBhciIpJHN0YXRlCiAgICAgIH0pICU+JSB1bmlxdWUoKQogICAgICBpZiAobGVuZ3RoKGNoaWxkLnN0YXRlcykgPT0gMSAmICFhbnlOQShjaGlsZC5zdGF0ZXMpKSB7CiAgICAgICAgc3RhdGUgPC0gY2hpbGQuc3RhdGVzCiAgICAgIH0gZWxzZSB7CiAgICAgICAgc3RhdGUgPC0gTkEKICAgICAgfQogICAgICBhdHRyKG5vZGUsICJub2RlUGFyIikgPC0gYXBwZW5kKGF0dHIobm9kZSwgIm5vZGVQYXIiKSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBsaXN0KHN0YXRlID0gc3RhdGUpKQogICAgfQogICAgbm9kZQogIH0sIGRpcmVjdGlvbiA9ICJ1cCIpCiAgIyBicm93c2VyKCkKICBwIDwtIGdncmFwaChkZW5kcm8sICJkZW5kcm9ncmFtIiwgY2lyY3VsYXIgPSBUUlVFKSArCiAgICBnZW9tX2VkZ2VfZWxib3coYWVzKGNvbG9yID0gbm9kZTIuc3RhdGUpKSArCiAgICBnZW9tX25vZGVfcG9pbnQoYWVzKGZpbHRlciA9IGxlYWYsIGNvbG9yID0gdGltZS5pbmRleCkpICsKICAgIHNjYWxlX2NvbG9yX2Rpc3RpbGxlcihwYWxldHRlID0gIllsT3JSZCIpICsKICAgIHRoZW1lX2dyYXBoKGJhc2VfZmFtaWx5ID0gIkhlbHZldGljYSIpICsKICAgIHRoZW1lKGFzcGVjdC5yYXRpbyA9IDEsIGxlZ2VuZC5rZXkuaGVpZ2h0ID0gdW5pdCgxMCwgInBvaW50cyIpKQp9KQpwbG90X2dyaWQocGxvdGxpc3QgPSB0cmVlcywgbmNvbCA9IDIsIGxhYmVscyA9IG5hbWVzKHRyZWVzKSkKYGBgCgo=